题解 P3366 【【模板】最小生成树】
muyang_233
·
·
个人记录
这道题，是最小生成树的模板题。
我们来看一个解决最小生成树的常用算法——Kruskal。
Kruskal算法概述
Kruskal算法非常易于理解，需要借助并查集，具体思路如下：
$\ \ \ \ \ \ \ $我们只要把边按边权升序排序（对应“最小”），
$\ \ \ \ \ \ \ $随后对于每条边，看这各边所对应的两个节点是否在同一集合内，如果不在（对应“生成树”，树需要无环），就合并两个节点所对应的集合，并将答案加上边权。
具体来说，是这样的：
1. 将每条边的信息（两点一边）存入一个结构体数组内，将该数组按边权升序排序；
2. 初始化并查集（所有节点的集合代表都是其本身）；
3. 遍历每条边，如果该边的两个节点不在一个集合内（如果在一个集合内说明这两点已经相连，再加边将会出现环），就将两点所对应的集合合并，并将答案加上边权；
4. 最后输出答案。
我们来看AC代码：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 5000+5
#define MAX_M 200000+5
struct edge{
int start,end;
int length;
}Edge[MAX_M];
int fa[MAX_N];
int n,m;
bool cmp(edge a,edge b){//cmp函数，将每条边按边权升序排序
return a.length<b.length;
}
void init(){//初始化并查集，所有节点的集合代表都是其本身
for (int i=1;i<=n;i++)
fa[i]=i;
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
//求每个点的集合代表
//注意这里的路径压缩（fa[x]=get(fa[x])），这能大幅度减少时间
int Kruskal(){
sort(Edge+1,Edge+m+1,cmp);//排序
int sum=0;
init();//初始化并查集
for (int i=1;i<=m;i++){//遍历每条边
int start=Edge[i].start,end=Edge[i].end;
start=get(start);end=get(end);
if (start!=end){//如果两点不在一个集合内
fa[end]=start;//合并
sum+=Edge[i].length;//答案加上边权
}
}
return sum;//返回，到主函数输出
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&Edge[i].start,&Edge[i].end,&Edge[i].length);//输入每条边的信息
printf("%d\n",Kruskal());//输出
return 0;
}
```