最小生成树 Kruskal 算法 简单题

2024-06-15 19:48
文章标签 算法 简单 最小 生成 kruskal

本文主要是介绍最小生成树 Kruskal 算法 简单题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

生成树 无向连通图G的一个子图如果是一棵包含G的所有顶点的树

Kruskal算法 并查集的应用 

边的长度排序 选取当前最小距离的边 加入图中 看是否能够构成环（用并查集判断是否有环）  没有环就将边加入到图中 

ZOJ  1203  给出n个点的坐标  求连接n个点所需线路长度总和的最小值

除了要计算下两点之间的距离外 就是裸的Kruskal

贴个代码就好

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;struct edge
{int u,v;double len;bool operator <(const edge p)const{return len<p.len;}
};
edge e[5000];
double x[110],y[110];
double sum;
int n,m;
int parent[110];//根节点double LEN(int i,int j)
{double l=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));return l;
}void init()
{for(int  i=0;i<n;i++)parent[i]=-1;
}
//并查集
int Find(int x)//       查找并返回根节点
{int p;for(p=x;parent[p]>=0;p=parent[p]);while(p!=x)//压缩路径{int tmp=parent[x];parent[x]=p;x=tmp;}return p;
}void Union(int R1,int R2)//将两个不同集合的元素进行合并
{int r1=Find(R1); int r2=Find(R2);int tmp=parent[r1]+parent[r2]; //两个集合结点个数只喝（负数）if(parent[r1]>parent[r2]) //加权法则 将子节点更多的节点作为父节点{parent[r1]=r2;parent[r2]=tmp;}else{parent[r2]=r1;parent[r1]=tmp;}
}void Kruskal()
{int num=0;  //已经选用边的个数int x,y;    //存储边的两个顶点init();for(int i=0;i<m;i++){x=e[i].u; y=e[i].v;if(Find(x)!=Find(y)){sum+=e[i].len;num++;Union(x,y);}if(num>=(n-1)) break;}
}int main()
{
//freopen("ceshi.txt","r",stdin);int cs=1;while(scanf("%d",&n)!=EOF){if(n==0)  break;for(int i=0;i<n;i++)scanf("%lf%lf",&x[i],&y[i]);int cnt=0;m=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){e[cnt].u=i; e[cnt].v=j;e[cnt].len=LEN(i,j);cnt++;m++;}sort(e,e+m);sum=0.0;Kruskal();if(cs>1)  puts("");printf("Case #%d:\n",cs);printf("The minimal distance is: %.2lf\n",sum);cs++;}return 0;
}


ZOJ 1542

给出n个点 m条边的长度  求出连接n个点最短的长度和

输出选取边中节点的值

直接Kruskal算法就好   注意parent数组的初始化

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;int n,m;
struct edge
{int u,v;int len;bool operator <(const edge p)const{return len<p.len;}
};
edge e[15010];
int parent[1010];
int note[1010];void init()
{for(int i=0;i<=n;i++)parent[i]=-1;//注意 因为每个节点的值都是大于等于1小于等于n的 所有n要包括其中
}int Find(int x)
{int p;for(p=x;parent[p]>=0;p=parent[p]);while(p!=x){int tmp=parent[x];parent[x]=p;x=tmp;}return p;
}void Union(int R1,int R2)
{int r1=Find(R1),r2=Find(R2);int tmp=parent[r1]+parent[r2];if(parent[r1]>parent[r2]){parent[r1]=r2;parent[r2]=tmp;}else{parent[r2]=r1;parent[r1]=tmp;}
}void Kruskal()
{init();int mx=-1;int x,y;int cnt=0;for(int i=0;i<m;i++){x=e[i].u; y=e[i].v;if(Find(x)!=Find(y)){mx=max(mx,e[i].len);note[cnt++]=i;Union(x,y);}if(cnt>=(n-1)){printf("%d\n",mx);break;}}
}int main()
{
//freopen("ceshi.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<m;i++){int x,y,l;scanf("%d%d%d",&x,&y,&l);e[i].u=x; e[i].v=y;e[i].len=l;}sort(e,e+m);
//        cout<<"whwhw"<<endl;Kruskal();printf("%d\n",n-1);for(int i=0;i<n-1;i++){int tmp=note[i];printf("%d %d\n",e[tmp].u,e[tmp].v);}}return 0;
}


又水了两个题。。。

zoj 1406

没什么好说的  主要是读入的问题 

我一开始用 scanf 读入 因为里面有字符 有数字 有空格 换行 我就一个个的去读入 但是有问题 不造为什么

用cin直接读入就对了。。。郁闷。。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;
int n;
struct edge
{int u,v;int len;bool operator<(const edge p)const{return len<p.len;}
};
edge e[80];
int parent[27];
int res;
int cnt;//边的条数void init()
{for(int i=0;i<27;i++)parent[i]=-1;
}int Find(int x)
{int p;for(p=x;parent[p]>=0;p=parent[p]);while(p!=x){int tmp=parent[x];parent[x]=p;x=tmp;}return p;
}void Union(int R1,int R2)
{int r1=Find(R1),r2=Find(R2);int tmp=parent[r1]+parent[r2];if(parent[r1]>parent[r2]){parent[r1]=r2;parent[r2]=tmp;}else{parent[r2]=r1;parent[r1]=tmp;}
}void Kruskal()
{init();int num=0;for(int i=0;i<cnt;i++){int x,y;x=e[i].u; y=e[i].v;if(Find(x)!=Find(y)){res+=e[i].len;num++;Union(x,y);}if(num>=n-1)  break;}
}int main()
{
//freopen("ceshi.txt","r",stdin);while(cin>>n){if(n==0)  break;cnt=0;for(int i=0;i<n-1;i++){char a,b;int x,y,l;cin>>a>>y;x=a-'A';//从0开始for(int j=0;j<y;j++){cin>>b>>l;int z=b-'A';e[cnt].u=x; e[cnt].v=z;e[cnt].len=l;cnt++;}
//            scanf("\n");}res=0;
//        cout<<"11111111"<<endl;sort(e,e+cnt);Kruskal();
//        cout<<"222"<<endl;printf("%d\n",res);}return 0;
}


ZOJ 1372 

没什么说的  主要是判重的问题  

我是用三维map存储状态  直接判断就可以了。。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64using namespace std;
map<int,map<int,int> > mp;
int n,m;
int res;
int parent[60];
struct edge
{int u,v;int len;bool operator<(const edge p)const{return len<p.len;}
};
edge e[3000];void init()
{for(int i=0;i<=n;i++)parent[i]=-1;
}int Find(int x)
{int p;for(p=x;parent[p]>=0;p=parent[p]);while(p!=x){int tmp=parent[x];parent[x]=p;x=tmp;}return p;
}void Union(int R1,int R2)
{int r1=Find(R1),r2=Find(R2);int tmp=parent[r1]+parent[r2];if(parent[r1]>parent[r2]){parent[r1]=r2;parent[r2]=tmp;}else{parent[r2]=r1;parent[r1]=tmp;}
}void Kruskal()
{init();int num=0;for(int i=0;i<m;i++){int x,y;x=e[i].u; y=e[i].v;if(Find(x)!=Find(y)){res+=e[i].len;num++;Union(x,y);}if(num>=n-1)  break;}
}int main()
{
//freopen("ceshi.txt","r",stdin);
//int cs=1;while(scanf("%d",&n)!=EOF){if(n==0) break;scanf("%d",&m);for(int i=1;i<=50;i++)for(int j=1;j<=50;j++)mp[i][j]=0;for(int i=0;i<m;i++){int x,y,l;scanf("%d%d%d",&x,&y,&l);if(!mp[x][y]){e[i].u=x; e[i].v=y;e[i].len=l;mp[x][y]=1;}else{e[i].len=min(l,e[i].len);}}sort(e,e+m);res=0;Kruskal();printf("%d\n",res);
//        cout<<"case "<<cs++<<endl;}return 0;
}




这篇关于最小生成树 Kruskal 算法 简单题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1064409。

相关文章

基于Python实现一个简单的题库与在线考试系统

基于Python实现一个简单的题库与在线考试系统

《基于Python实现一个简单的题库与在线考试系统》在当今信息化教育时代,在线学习与考试系统已成为教育技术领域的重要组成部分,本文就来介绍一下如何使用Python和PyQt5框架开发一个名为白泽题库系... 目录概述功能特点界面展示系统架构设计类结构图Excel题库填写格式模板题库题目填写格式表核心数据结构
阅读更多...
Python实现自动化Word文档样式复制与内容生成

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现：样式与表格的深度复制1. 表格复制（含样式与内容）2
阅读更多...
python如何生成指定文件大小

python如何生成指定文件大小

《python如何生成指定文件大小》：本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
Maven项目中集成数据库文档生成工具的操作步骤

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin（推荐）的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事
阅读更多...
MybatisX快速生成增删改查的方法示例

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2
阅读更多...
windows和Linux安装Jmeter与简单使用方式

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》：本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设
阅读更多...
使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
使用Python自动化生成PPT并结合LLM生成内容的代码解析

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤：代码片段：2. 应用 JSON 样式到
阅读更多...
SpringBoot实现二维码生成的详细步骤与完整代码

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2