最小生成树

1.生成树

对于一张无向连通图G，它的一个连通子图,含有图中全部n个顶点，但只有足以构成一棵树的n-1条边，那么就称这个子图为G的生成树

2.最小生成树

边的权值加起来最小的生成树

3.求出最小生成树

3.1.破圆法

简称有环就破

3.2.kruskal

1.去除所有边，留点
2.边拽权值排序
3.依此加回去（无环）

3.2.1题目类型

题目描述：给出一个无向图，求出最小生成树，如果该图不连通，则输出orz。

输入：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出：
7

题解：可以用kruskal，具体过程如下：
先根据边权进行排序
逐条边加入（从小到大）
加入边的时候进行判断
如果加上这条边成环了，则不要这条边（并查集）
否则要这条边
所以边判断结束后终止（或加入n-1条边之后停止）
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e5+10;
int n,m,f[maxn];
struct aaa{
	int x,y,z;
}s[maxn];
bool cmp(aaa a,aaa b){
	return a.z<b.z;
}
int find(int x){
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
int kruskal(){
	sort(s+1,s+m+1,cmp);
	int cnt=0,ans=0;
	for(int i=1;i<=m;i++){
		int a=find(s[i].x),b=find(s[i].y);
		if(a==b) continue;
		f[a]=b;
		ans+=s[i].z;
		cnt++;
		if(cnt==n-1){
			cout<<ans<<"\n";
			return ans;
		} 
	}
	cout<<"orz\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>s[i].x>>s[i].y>>s[i].z;
	}
	kruskal();
	return 0;
}