Boruvka 求最小生成树

这玩意好像还是有点用的，主要是思想可以学习一下，而且好像有的题也只能用它。

原理：

一开始将每个点都看成一个集合，每次遍历找到每个集合和其他集合连边的边的最小值，然后枚举这些边，若左右端点不在同一个集合中，将这两个集合合并，重复操作至不能操作，最后就能求出最小生成树。

正确性：

应该是和 kruskal 一样的。

复杂度证明：

因为一条边只有两个端点，所以一条边最多属于两个集合，所以设有 $x​$ 个集合，我们找到的不同的边的个数至少是 $\lceil \frac{x}{2} \rceil​$，所以每次做集合合并操作集合个数至少少一半，这里的复杂度是 $O(\log n)​$，每次操作我们要遍历一遍所有边，时间复杂度 $O(m)​$，所以总时间复杂度是 $O(m\log n)​$ 的。

实现：

记录一个 best 数组表示当前这个集合 $i$ 能连出去的最小边权的边是哪条边，每次操作先遍历一遍边，找出每个集合的 best 数组，最后看是否能将这些边加入边集，如果可以就加入。

P3366

code：

const int N=5007,M=2e5+7;
int n,m;
struct edges{
	int u,v,w;
	edges(){ u=v=w=0; }
	edges(int U,int V,int W){ u=U,v=V,w=W; }
	bool operator <(const edges A) const { return w<A.w; }
}e[M];
int best[N];
int p[N];
inline void init(int n){ for(int i=1;i<=n;i++) p[i]=i; }
inline int find(int x){ return x!=p[x]?p[x]=find(p[x]):x; }
int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	rd(n,m);
	init(n);
	for(int i=1;i<=m;i++) rd(e[i].u,e[i].v,e[i].w);
	int ans=0,cnt=0;
	bool flag=1;
	while(flag){
		flag=0;
		for(int i=1;i<=n;i++) best[i]=0;
		for(int i=1;i<=m;i++){
			int x=find(e[i].u),y=find(e[i].v);
			if(x==y) continue;
			if(!best[x]||e[i].w<e[best[x]].w) best[x]=i;
			if(!best[y]||e[i].w<e[best[y]].w) best[y]=i;
		}
		for(int i=1;i<=n;i++){
			if(best[i]){
				int x=find(e[best[i]].u),y=find(e[best[i]].v);
				if(x==y) continue;
				cnt++,ans+=e[best[i]].w,flag=1,p[x]=y;
			}
		}
	}
	if(cnt==n-1) wt('\n',ans);
	else puts("orz");
	return 0;
}