最小生成树

Kruskal

Kruskal 求最小生成树是一种以边贪心的最小生成树算法。

设一张图的点数为 $n$，边数为 $m$。 观察一个图和它的最小生成树，发现在构造最小生成树的过程中，每一次是选择一条较小的边去连通，所以考虑贪心。 首先肯定是按边权从小到大排序，然后跑每一条边。如果这个边得起点和重点没有放进最小生成树的集中，就把他们放进集合，并将答案加入边权，总边数 $+1$。如果在跑的过程中，总边数达到 $n-1$，那么就说明这一个树构造好了，可以直接

break

此时的问题就是，这个最小生成树集怎么维护？这里可以使用并查集做到 $O(\alpha(n))$ 的每次操作，只有把每个点开到并查集里，每次判断这一条边的起点和终点是否在一个集合里，是的话跳过，不是的话就合并。

总复杂度为排序的 $O(m\log m)$。

注意点 1.排序是注意是 $m$ 而不是 $n$。 2.注意初始化并查集。

code

cpp
Copy
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10;
struct node{
	int u,to;
	int w;
};
bool cmp(node a,node b){
	return a.w<b.w;
}
node e[N];
int n,m;
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);
}
void kruskal(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int ans=0;
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=e[i].u,to=e[i].to;
		int w=e[i].w;
		if(find(u)!=find(to)){
			//cout<<u<<' '<<to<<'\n';
			ans+=w;
			cnt++;
			merge(u,to);
			if(cnt==n-1)break;
		}
		
	}
	if(cnt<n-1)cout<<"orz";
	else cout<<ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].to>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	//for(int i=1;i<=m;i++)cout<<e[i].w<<' ';
	//cout<<'\n';
	kruskal();
	return 0;
}

Prim

以后再补。