最小生成树（学习笔记）
XichenOC
·
·
算法·理论
最小生成树kruskal
P3366 【模板】最小生成树
作用：
可以用来在一个无向连通图中找到一颗生成树，使其边权之和最小
算法原理：
# 完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=202410;
struct edge{
int u,v,w;
bool operator<(const edge &a)const{return w<a.w;}
}e[N];
int fa[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+1+m);
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
if(find(e[i].u)!=find(e[i].v)){
ans+=e[i].w;
merge(e[i].u,e[i].v);
cnt++;
}
}
if(cnt!=n-1){
cout<<"orz"<<endl;
return 0;
}
cout<<ans<<endl;
}
```
# 练习：
[$1.$P1195 口袋的天空](https://www.luogu.com.cn/problem/P1195) [**题解**](https://www.luogu.com.cn/article/a108e723)
[$2.$P1194 买礼物](https://www.luogu.com.cn/problem/P1194) [**题解**](https://www.luogu.com.cn/article/2l8nmdkm)
[$3.$P1550 [USACO08OCT] Watering Hole G](https://www.luogu.com.cn/problem/P1550) [**题解**](https://www.luogu.com.cn/article/0qkf56nh)
[$4.Cheap Robot$](https://www.luogu.com.cn/problem/CF1253F) [**题解**](https://www.luogu.com.cn/article/3aql7yl6)
[$5.P3623 [APIO2008]$ 免费道路](https://www.luogu.com.cn/problem/P3623) [**题解**](https://www.luogu.com.cn/article/vh423if9)
[$6$.P1340 兽径管理](https://www.luogu.com.cn/problem/P1340) [**题解**](https://www.cnblogs.com/XichenOC/p/18686664)