Kruskal
2019-08-19
RT
Kruskal是一种用于建立最小生成树(MST)的算法，同理的还有Prim算法。与Kruskal算法相关的还有并查集，也就是说Kruskal的实现需要并查集（可参考蒟蒻的OI笔记）。
思想
1.将图中的所有边按权值从小到大排序
2.遍历每一条边，检查两边的点是否在同一集合（或者说在同一棵树上）。如果在，则跳过；如果不在，就合并（此处充分的利用并查集的查找和合并两大功能），此时的这条边叫做“安全边”。
Tips
为什么如此进行就可以建立最小生成树呢？
每次遍历时，当前的边一定是最小的边（最起码当前是）。
情况1：当前的边的两点在同一集合（或者说在同一棵树上），那么加入这条边则多此一举。
情况2：当前的边的两点不在同一集合（或者说不在同一棵树上）。如果不加入这条边，还能建立完整的生成树的话，那么势必有一条或多条边来等效此边，但是此边是当前最小的，所以等效的部分一定是大于此边的；如果不加入这条边，建立不了完整的生成树，那就更不用说了（滑稽.jpg)。所以一定要加入此边。
Code
int p[]; //p[i]表示i的父亲节点
struct note{
int u,v,w;
}d[]; //边的信息，u，v——端点，w——权值
int n,m; //n——点数，m——边数
int ans; //权值和
bool cmp(const note &a,const note &b){
return a.w<b.w;
}
int find(int s){
if(s!=f[s]) f[s]=find(f[s]);
return f[s];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i].u,&d[i].v,&d[i].w);
sort(d+1,d+1+n,cmp);
for(int i=1;i<=m;i++){
int e,r;
e=find(d[i].u);
r=find(d[i].v);
if(e!=r) p[r]=e,ans+=d[i].w;
}
printf("%d",ans);
return 0;
}
其实这只是Kruskal的大体轮廓，还得具体情况具体分析。