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

相关文章

IDEA自动生成注释模板的配置教程

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注
阅读更多...
Python如何自动生成环境依赖包requirements

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》：本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
使用Python开发一个简单的本地图片服务器

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经
阅读更多...
Java利用docx4j+Freemarker生成word文档

Java利用docx4j+Freemarker生成word文档

《Java利用docx4j+Freemarker生成word文档》这篇文章主要为大家详细介绍了Java如何利用docx4j+Freemarker生成word文档,文中的示例代码讲解详细,感兴趣的小伙伴... 目录技术方案maven依赖创建模板文件实现代码技术方案Java 1.8 + docx4j + Fr
阅读更多...
Java编译生成多个.class文件的原理和作用

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类（常规内部类）局部内部类（方法内部类）匿名内部类二、
阅读更多...
使用Jackson进行JSON生成与解析的新手指南

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON（序列化）2.2 JSON 转对象（反序列化）3.
阅读更多...
Mysql表的简单操作(基本技能)

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例：修改表在数据库中，表的操作主要
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2