@TOC
下面让我们来具体介绍一下
概念
克鲁斯卡尔是一种求连通图的最小生成树的算法（用最少的路线连接所有点），它的时间复杂度为 O（nloge）n 为边数
原理
通过以结构体中的权值为排序对象来排序结构体，通过 getf（）函数来寻找有没有共同联通点，有的话就跳过，没有的话就进行加边操作并且记录答案，详细内容在下文实现方式中会讲到。下面让我们用图的形式感受一下：
这里可以发现，1-2 最小值为 1，所以连接这条线，并且 2 的“爹”=1；
找完最小的边找第二条边，这时候 1 和 4 也就连通了
连接这条边后，他们的爹都统一了，所以就全部连通了
所以现在所有点的爹都有同一个值，那么他们就联通了在算法中会通过寻找每一个值的爹来判断他们是否连通，如果连通那么就不管，如果没连通，就要进行加边操作，并且记录答案。
作用
通俗易懂的来说，就是用最小的权值连通图中所有点
实现方式
<font color="red" size="4">下面来看一道题</font>P3366 【模板】最小生成树题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式第一行包含两个整数 N,M 表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 X_i,Y_i,Z_i，表示有一条长度为 Z_i的无向边连接结点 X_i,Y_i 输出格式如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例输入 #1 复制 4 51 2 21 3 21 4 32 3 43 4 3 输出 #1 复制 7 说明/提示数据规模：
对于 20%20% 的数据，N≤5，M≤20。
对于 40%40% 的数据，N≤50，M≤2500。
对于 70%70% 的数据 N≤500，M≤10^4 对于 100%100% 的数据：1≤N≤5000，1≤M≤2×10^5，1≤Z ≤10 ^4
样例解释：所以最小生成树的总边权为 2+2+3=72+2+3=7。这是一道经典的最小生成树模板题，具体细节让我们在代码中体现
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;struct node{ int u,v,w,next;
bool operator < (const node &a)const{ return w<a.w;//这里时以w为比较对象进行排序的意思，和下文sort一起用 }
}e[1010101];int m,n;int f[1010101];int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]);//这里就是上文所说，可以理解为“找爹”，具体解释在此题代码下方}inline int kruskal(){ int val=0,cnt=0; sort(e+1,e+1+m);//无论如何记得排序 for(int i=1;i<=m;i++){ int u=e[i].u,v=e[i].v;//如果两个点没有连通那么就记录数据 int xx=getf(u); int yy=getf(v); if(xx!=yy){ cnt++,val+=e[i].w,f[xx]=yy;//边数加以，记录w，同步两点的“爹” } if(cnt==n-1) return val; } return -1;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ cin>>e[i].u>>e[i].v>>e[i].w;//因为这里是单项图，所以可以直接输入 } int x=kruskal(); if(x==-1) cout<<"orz"; else cout<<x; return 0;}
复制代码
<font color="red" size="5"> getf 函数详解</font>
getf(int x){ return x==f[x]?x:f[x]=getf(f[x]);}这里是说当点x等于找爹后的值，说明已经找到头了，如果是这样就return x。如果不是这样就继续找爹，所以f[x]要等于getf(f[x])，需要去以当前找到的爹为递归对象去找爷，以此类推直到找到祖宗。。。
复制代码
全部介绍完了，下面来总结一下克鲁斯卡尔的模板吧
struct edge{ int u,v,w,next//next在这里暂时用不上，以后学习其他图论算法会用到 bool operator <(const edge &a)const{ return w<a.w//这里是从小到大排序，反过来就是从大到小排序 }}e[100005]int ecnt=0;//记录边数void add(int u,int v,int w){ e[++ecnt].u=u; e[ecnt].w=w; e[ecnt].v=v;}getf(int x){return x==f[x]?x:f[x]=getf(f[x]);} int kruskal(){ int val=0,cnt=0; sort(e+1,e+1+m); for(int i=1;i<=m;i++){ int u=e[i].u,v=e[i].v; int xx=getf(u); int yy=getf(v); if(xx!=yy){ cnt++,val+=e[i].w,f[xx]=yy; } if(cnt==n-1) return val; } return -1;}int main(){ cin>>n>>m; for(i——m){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } for(i--n){ f[i]=i;//初始化，使每个点的爹都是自己 }}
复制代码
例题讲解
例题 1
营救题目背景“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……
题目描述妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s 区。
该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。
输入格式第一行有四个用空格隔开的 n，m，s，t，其含义见【题目描述】。
接下来 m 行，每行三个整数 u, v, w 表示有一条大道连接区 u 和区 v，且拥挤度为 w。
两个区之间可能存在多条大道。
输出格式输出一行一个整数，代表最大的拥挤度。
输入输出样例输入 #1 复制 3 3 1 31 2 22 3 11 3 3 输出 #1 复制 2 说明/提示数据规模与约定对于 30% 的数据，保证 n≤10。对于 60% 的数据，保证 n≤100。对于 100% 的数据，保证 1≤n≤10^4 ,1≤m≤2×10 ^4，w≤10 ^4，1≤s,t≤n。且从 s 出发一定能到达 t 区。样例输入输出 1 解释小明的妈妈要从 1 号点去 3 号点，最优路线为 1->2->3。来看看题解
#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int n,m; struct edge{ int u,v,w; bool operator <(const edge &a)const{ return w<a.w; } }e[1010101];int s,t;int ecnt=0;void add(int u,int v,int w){ e[++ecnt].w=w; e[ecnt].v=v; e[ecnt].u=u;}int f[1010101];int getf(int x){ return x==f[x]?x:f[x]=getf(f[x]);}int main(){ cin>>n>>m; cin>>s>>t; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } for(int i=1;i<=n;i++){ f[i]=i; } sort(e+1,e+1+ecnt); //克鲁斯卡尔 for(int i=1;i<=ecnt;i++){ int u=getf(e[i].u); int v=getf(e[i].v); if(u!=v){ f[u]=v; } if(getf(s)==getf(t)){//注意这里改一下就好，这道题规定了起点终点 cout<<e[i].w; return 0; } }
}
复制代码
例题 2
买礼物题目描述又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。但是，商店老板说最近有促销活动，也就是：如果你买了第 I 样东西，再买第 J 样，那么就可以只花 K_{I,J}元，更巧的是，K_{I,J}竟然等于 K_{J,I}。现在明明想知道，他最少要花多少钱。输入格式第一行两个整数，A,B。接下来 B 行，每行 B 个数，第 I 行第 J 个为 K_{I,J}。我们保证 K_{I,J}=K_{J,I}并且 K_{I,I}==0。特别的，如果 K_{I,J}=0，那么表示这两样东西之间不会导致优惠。输出格式一个整数，为最小要花的钱数。
输入输出样例输入 #1 复制 1 10
输出 #1 复制 1 输入 #2 复制 3 30 2 42 0 24 2 0 输出 #2 复制 7 说明/提示样例解释 2。先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）数据规模对于 30%30% 的数据，1≤B≤ 10。对于 100%100% 的数据，1≤B≤500,0≤A,K I,J≤1000。<font color=”green“>提示一下，可以横距图论的想法来解决这道题，起点 i，终点 j，权值 k[i，j]</font>来看题解
#include<cmath>#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>
using namespace std;int A,B;int mapp[1005][1005];int f[1010101];struct edge{ int u,v,w,next; bool operator <(const edge &a)const{ return w<a.w; }}e[1010011];int ecnt=0;void add(int u,int v,int w){ e[++ecnt].u=u; e[ecnt].v=v; e[ecnt].w=w;}int getf(int x){ return x==f[x]?x:f[x]=getf(f[x]);}int main(){ cin>>A>>B; for(int i=1;i<=B;i++){ for(int j=1;j<=B;j++){ int x; cin>>x; if(x){//需要判断一下是否优惠，不优惠直接把原价add进去 add(i,j,x); }else{ add(i,j,A); } } } for(int i=1;i<=B;i++){ f[i]=i; } sort(e+1,e+1+ecnt); int cnt=0,w=0; //克鲁斯卡尔 for(int i=1;i<=ecnt;i++){ int u=getf(e[i].u); int v=getf(e[i].v); if(u!=v){ f[u]=v; cnt++; w+=e[i].w;//熟不熟悉。。。 } if(cnt==B-1){//b个点，b-1条边 break; } } if(B*A<w+A){ cout<<B*A; }else cout<<w+A;}
复制代码
这两题做完，想必各位对克鲁斯卡尔算法也有了清楚的认识，下面还有一些题目和题解可以供各位学习。今天就到这里了，再会！！！
更多克鲁斯卡尔算法题解可以看下方链接口袋的天空，部落划分无线通讯网Building Roads S拆地毯
<font color="blue" size="5">如有疑问可以私信奥，如有错误私信我会及时做出改正。喜欢的话就关注一下吧，你的关注是我创作的动力^^</font>
评论