最小生成树 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。

相关文章

Java使用Javassist动态生成HelloWorld类

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC
阅读更多...
Python 基于http.server模块实现简单http服务的代码举例

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python
阅读更多...
Python从Word文档中提取图片并生成PPT的操作代码

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中，我们经常需要从 W
阅读更多...
C#使用Spire.XLS快速生成多表格Excel文件

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压：从3秒到0.5秒的质变1.2 批量操作的优雅
阅读更多...
Python使用python-pptx自动化操作和生成PPT

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看
阅读更多...
python连接sqlite3简单用法完整例子

python连接sqlite3简单用法完整例子

《python连接sqlite3简单用法完整例子》SQLite3是一个内置的Python模块,可以通过Python的标准库轻松地使用,无需进行额外安装和配置,：本文主要介绍python连接sqli... 目录1. 连接到数据库2. 创建游标对象3. 创建表4. 插入数据5. 查询数据6. 更新数据7. 删除
阅读更多...
Jenkins的安装与简单配置过程

Jenkins的安装与简单配置过程

《Jenkins的安装与简单配置过程》本文简述Jenkins在CentOS7.3上安装流程,包括Java环境配置、RPM包安装、修改JENKINS_HOME路径及权限、启动服务、插件安装与系统管理设置... 目录www.chinasem.cnJenkins安装访问并配置JenkinsJenkins配置邮件通知
阅读更多...
在ASP.NET项目中如何使用C#生成二维码

在ASP.NET项目中如何使用C#生成二维码

《在ASP.NET项目中如何使用C#生成二维码》二维码（QRCode）已广泛应用于网址分享,支付链接等场景,本文将以ASP.NET为示例,演示如何实现输入文本/URL,生成二维码,在线显示与下载的完整... 目录创建前端页面（Index.cshtml）后端二维码生成逻辑（Index.cshtml.cs）总结
阅读更多...
Python实现数据可视化图表生成(适合新手入门)

Python实现数据可视化图表生成(适合新手入门)

《Python实现数据可视化图表生成(适合新手入门)》在数据科学和数据分析的新时代,高效、直观的数据可视化工具显得尤为重要,下面：本文主要介绍Python实现数据可视化图表生成的相关资料,文中通过... 目录前言为什么需要数据可视化准备工作基本图表绘制折线图柱状图散点图使用Seaborn创建高级图表箱线图热
阅读更多...
SQLServer中生成雪花ID(Snowflake ID)的实现方法

SQLServer中生成雪花ID(Snowflake ID)的实现方法

《SQLServer中生成雪花ID(SnowflakeID)的实现方法》：本文主要介绍在SQLServer中生成雪花ID(SnowflakeID)的实现方法,文中通过示例代码介绍的非常详细,... 目录前言认识雪花ID雪花ID的核心特点雪花ID的结构（64位）雪花ID的优势雪花ID的局限性雪花ID的应用场景
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2