最小生成树

最小生成树即一个连通图（要有权值）中一棵边权和最小且包含所有顶点的树（我们知道连接

n

个顶点最少要

n-1

，又由于我们要树的权值最小，所以我们贪心的只选择

n-1

条边），那么这棵树就被称为最小生成树。

Kruskal算法

首先我们可以把一个图看为没有任何边的森林。我们最后要让它们构成一棵树（即没有回路，且连通），我们很容易的想到并查集。那现在后面就很好得到了，我们可以尽量贪心的选择权值(边权)最小的一个节点合并，不过注意判断是否在一个集合，不然就不是一棵树了。

正确性证明：如果这棵树不是最小生成树则一定会有至少一条边不一样，且这条边小于原本选择的边，而由于是贪心思想，则这个边一定会在前面被加入树中。

Code

CPP

#include<bits/stdc++.h>//problem:P3366 (algorithm: Kruskal)
using namespace std;
#define zjj long long
const int MAXN=1e6+5;
const int INF=1e9;
int T=1;
int n,m,st,en;
int idx,cnt,ans;
bool flag;
int f[MAXN];
struct S{
	int pre,nxt;
	int dis;		
}s[MAXN];
bool cmp(S a,S b){
	return a.dis<b.dis;
}
void init(){
	for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){//路径压缩，查找根节点
	if(x==f[x]) return x;
	f[x]=find(f[x]);
	return f[x];
}
void Union(int x,int y){//合并
	if(find(x)==find(y)) return ;
	f[find(y)]=find(x);
}
void kruskal(){//主题贪心部分
	for(int i=1;i<=m;i++){
		if(find(s[i].pre)!=find(s[i].nxt)){
			Union(s[i].pre,s[i].nxt);
			ans+=s[i].dis;
			cnt++;
		}
	}
}
void slove(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>s[i].pre>>s[i].nxt>>s[i].dis;
	}
	sort(s+1,s+m+1,cmp);//由于贪心选最小的，所以sort一下
	kruskal();
	if(cnt==n-1) cout<<ans<<endl;//合并n-1次后所有点都在一棵树上了，所以比联通。
	else cout<<"orz"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// cin>>T;
	while(T--){
		slove();	
	}
	return 0;//exit(0);
}
//thinking: link->学最小生成树有感

Prim算法

Prim一种基于dijkstra的最小生成树算法

学最小生成树有感

文章操作