题解 P3366 【【模板】最小生成树】
Fractures
2018-12-07 13:19:45
## 这是一篇讲kruskal的题解
看题解很多大佬只讲kruskal思路，我就来写写整个代码的思路
### 思路：
核心思想不是堆，不是查找，而是sort
我们可以这么想：因为是最小的路径，所以我们可以排序一下，把节点根据长度从小到达大排序一下
所以，我们先开个结构体来储存节点和边长（开结构体是为了方便sort排序）
```cpp
struct node{
int p1,p2,val;//p1是出发点，p2是目的地，val是路的长度
};
```
因为是根据节点排序，所以我们可以开个cmp函数
```cpp
int cmp(node &A,node &B){//不写取地址符也可以
return A.val<B.val;//保持路径小的在前面
}
```
那么问题来了：怎么不走重复的点呢？
这需要我们的并查集。这里我不多讲并查集了，不会的大佬可以参考[这个](https://www.luogu.org/blog/My-luoguBuoke-HZR/solution-p3367)
那么我们就可以写一个find函数，用来合并两个已经走过的点
```cpp
int find(int k){
if(f[k]==k)return k;
return f[k]=find(f[k]);//路径压缩
}
```
然后再sort排序，整个代码就成型了
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int f[5001];
int find(int k){
if(f[k]==k)return k;
return f[k]=find(f[k]);
}
struct node{
int p1,p2,val;
};
int cmp(node &A,node &B){
return A.val<B.val;
}
node qwq[200001];
int ans,cnt;//cnt是用来判断能不能联通
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&qwq[i].p1,&qwq[i].p2,&qwq[i].val);
}
for(int i=1;i<=5000;i++)f[i]=i;//初始化
sort(qwq+1,qwq+m+1,cmp);//sort排序
for(int i=1;i<=m;i++){
if(find(qwq[i].p1)!=find(qwq[i].p2)){
cnt++;
f[find(qwq[i].p1)]=find(qwq[i].p2);//合并
ans+=qwq[i].val;
}
if(cnt==n-1){
printf("%d",ans);
return 0;
}
}
printf("orz\n");//不能联通就输出orz,但是好像测试点中没有不联通的数据
return 0;
}
```