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

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2