详解
Borůvka 算法的本质是一种多路 Prim 最小生成树算法，复杂度 (mlog n)，但劣于 Kruskal 的 (log)
算法功能：求简单图的最小生成树
算法流程是这样的
考虑当前的图（未连边），一定由若干连通块构成，我们考虑连接连通块
可以想到，对于任意一个连通块，一定应该与尽可能优的连通块连边，并且，如果该连通块不在本操作连边，无论以后的操作如何改变其他连通块的状态，连通块总是单调不减的，花费也一定是单调不减的，因此直接在本操作连边即可
根据上述原理，可以尝试枚举所有边，然后尝试用这条边去更新端点所在连通块，对于连通块，则选择一个最优的边来更新自身
可以想到在一次操作中，总有至少一半的连通块被连接而消失，复杂度 (mlog n)
需要注意的有以下几点
- “最优的边” 在这里必须是严格的，即你需要保证不存在 (i,jin [1,m])，使得两条边 (e_i=e_j)，至于为什么要这么做，一个经典的例子是重边，如果现在有 ((1,2,w=1)) 和 ((2,1,w=1)) 两条边，这两条边使得连通块 (1) 和连通块 (2) 都能被更新到，这样在合并的时候会连出环来，保证严格的最优性一般采用编号做第二关键字的办法
- 当然，你在无向图上跑最小生成树也会连出环，这个时候的解决办法是你在第二个循环里合并连通块之前判一下
Borůvka 需要判的东西比较多，注意不要漏掉
P3366 【模板】最小生成树
#include<bits/stdc++.h> using namespace std; int n,m; int best[100001]; struct edge{ int from,to,w; int id; bool used; bool operator <(const edge&A)const{ if(w==A.w) return id<A.id; return w<A.w; } }; vector<edge>e={{0,0,0,0,true}}; struct dsu{ int fa[100001]; void clear(){ for(int i=1;i<=n;++i){ fa[i]=i; } } int find(int id){ if(id==fa[id]) return id; return fa[id]=find(fa[id]); } bool samefa(int x,int y){ int fx=find(x),fy=find(y); return fx==fy; } bool join(int x,int y){ int fx=find(x),fy=find(y); if(fx==fy) return false; fa[fx]=fy; return true; } }d; int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;++i){ int x,y,z; cin>>x>>y>>z; e.push_back({x,y,z,i,false}); } d.clear(); int ans=0,tot=0; while(1){ bool flag=false; memset(best,0,sizeof best); for(edge i:e){ if(i.used or d.samefa(i.from,i.to)) continue; int tmp=d.find(i.from); int tmp2=d.find(i.to); if(best[tmp]==0 or i<e[best[tmp]]){ best[tmp]=i.id; } if(best[tmp2]==0 or i<e[best[tmp2]]){ best[tmp2]=i.id; } } for(int i=1;i<=n;++i){ if(d.find(i)==i){ if(best[i]!=0 and e[best[i]].used==false){ e[best[i]].used=true; ans+=e[best[i]].w; tot++; d.join(e[best[i]].from,e[best[i]].to); flag=true; } } } if(!flag) break; } if(tot!=n-1) cout<<"orz"; else cout<<ans; } 使用
显然，Borůvka 在稠密图上的表现不如 Prim，在稀疏图上的表现不如 Kruskal
那要这玩意有什么用吗
是因为 Borůvka 适用于一类特殊条件
这类特殊条件形如 给你一个完全图，完全图上的边权可以通过端点的点权经过某种计算得出，求最小生成树
这样的条件充分利用了 Borůvka 只会合并 (log n) 次的性质，这是其他两个最小生成树算法做不到的
但是这并不意味着你套模板就行了，暴力 Borůvka 仍然在 (n^2log) 级别，需要一些有性质的图来优化算法（一般是快速找到最小边权）
星际联邦
完全图上每个点有点权 (a_i)，定义 ((u,v)(ult v)) 的边权为 (a_v-a_u)，求最小生成树
(大概绿-蓝)
我们在每一轮需要找到这个点向外到另一个联通块内的最小边。注意到当 (i) 固定时，最小边要么是前缀 ([1, i)) 的最大值取到的，要么是 ((i, n]) 内的后缀最小值取到的。我们只需要对每个前缀维护最大值，以及和最大值不在同一个联通块内的最大值，后缀同理，就可以快速求出该联通块向外的最小边
时间复杂度为 (O(n log n))
#include<bits/stdc++.h> using namespace std; const long long inf=0x3f3f3f3f3f3f3f3f; int n; int a[300005]; struct val_t{ long long val,pos; inline bool operator<(const val_t&A)const{ return val<A.val; } inline bool operator>(const val_t&A)const{ return val>A.val; } inline bool operator!=(const val_t&A)const{ return pos!=A.pos; } }; inline val_t max(val_t a,val_t b){ return a>b?a:b; } inline val_t min(val_t a,val_t b){ return a<b?a:b; } struct pairval_t{ val_t x,y; }; const val_t pos_inf={inf,0}; const val_t neg_inf={-inf,0}; inline pairval_t max(pairval_t a,pairval_t b){ pairval_t ans={max(a.x,b.x),neg_inf}; if(a.x!=ans.x and a.x>ans.y) ans.y=a.x; if(a.y!=ans.x and a.y>ans.y) ans.y=a.y; if(b.x!=ans.x and b.x>ans.y) ans.y=b.x; if(b.y!=ans.x and b.y>ans.y) ans.y=b.y; return ans; } inline pairval_t min(pairval_t a,pairval_t b){ pairval_t ans={min(a.x,b.x),pos_inf}; if(a.x!=ans.x and a.x<ans.y) ans.y=a.x; if(a.y!=ans.x and a.y<ans.y) ans.y=a.y; if(b.x!=ans.x and b.x<ans.y) ans.y=b.x; if(b.y!=ans.x and b.y<ans.y) ans.y=b.y; return ans; } struct pairval_t maxn[300001],minn[300001]; struct val_t val[300001]; inline val_t askmax(int x,int pos){ return (maxn[x].x.pos==pos)?maxn[x].y:maxn[x].x; } inline val_t askmin(int x,int pos){ return (minn[x].x.pos==pos)?minn[x].y:minn[x].x; } struct dsu{ int fa[300001]; inline void clear(){ for(int i=1;i<=n;++i){ fa[i]=i; } } int operator[](int id){ if(id==fa[id]) return id; return fa[id]=this->operator[](fa[id]); } }d; inline long long Roukusaka(){ long long ans=0; d.clear(); for(int i=1;i<=n;++i){ maxn[i].x={a[i],i}; maxn[i].y=neg_inf; minn[i].x={a[i],i}; minn[i].y=pos_inf; } for(int i=2;i<=n;++i){ maxn[i]=max(maxn[i-1],maxn[i]); } for(int i=n-1;i>=1;--i){ minn[i]=min(minn[i+1],minn[i]); } while(1){ bool flag=false; for(int i=1;i<=n;++i){ val[i]=pos_inf; } for(int i=1;i<=n;++i){ int now=d[i]; val_t p=askmin(i,now); val_t q=askmax(i,now); if(q.val!=-inf and a[i]-q.val<=val[now].val){ val[now]={a[i]-q.val,q.pos}; } if(p.val!=inf and p.val-a[i]<=val[now].val){ val[now]={p.val-a[i],p.pos}; } } for(int i=1;i<=n;++i){ if(d[i]==i){ if(d[val[i].pos]==i or val[i].val==inf) continue; d.fa[d[val[i].pos]]=i; ans+=val[i].val; flag=true; } } for(int i=1;i<=n;++i){ maxn[i].x={a[i],d[i]}; maxn[i].y=neg_inf; minn[i].x={a[i],d[i]}; minn[i].y=pos_inf; } for(int i=2;i<=n;++i){ maxn[i]=max(maxn[i-1],maxn[i]); } for(int i=n-1;i>=1;--i){ minn[i]=min(minn[i+1],minn[i]); } if(!flag) break; } return ans; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;++i){ cin>>a[i]; } cout<<Roukusaka(); } CF888G Xor-MST
完全图上每个点有点权 (a_i)，定义 ((u,v)(uneq v)) 的边权为 (a_u operatorname{xor} a_v)，求最小生成树
考虑放到 trie 树上维护异或和最值
码量还行，找个时间码了
(紫)
图
给定两颗带权无向树 (T_1,T_2)，定义 (dis_i(x,y)) 表示树 (T_i) 上 (x,y) 间的距离，现有一完全二分图，左部，右部分别有 (n) 个点，定义左部点 (i) 与右部点 (j) 之间的边权为 (maxlimits_{x=1}^n(dis_1(i,x)+dis_2(j,x)))，求完全二分图最小生成树
https://h.hszxoj.com/d/hztg/contest/6716222721518607d314c04f/file/graph.cpp
