一种另类的最小生成树（MST）算法：Boruvka算法
一种另类的最小生成树（MST）算法：Boruvka算法
这种算法是结合了Prim和Kruscal算法，适合于完全图或者稠密图。
具体思路是不断合并连通块：
- 初始每个点为一个连通块；
- 我们需要找到每个连通块到其他所有连通块的最小出边；
- 合并连通块，将边权统计进答案；
这个合并连通块的轮数不会超过log n \log{n}logn，这是显然的，那么复杂度主要在每一轮中找到每个连通块的最小出边上，假设这个时间复杂度为O ( T ) O(T)O(T)，那么总时间复杂度为O ( α ( n ) T log n ) O(\alpha(n)T\log{n})O(α(n)Tlogn)。
对于给出边的情况，可以像下面这样写：
#include <bits/stdc++.h> using namespace std; #define endl '\n' using ll=long long; struct DSU{ int n; vector<int> fa,sz; DSU(int n):n(n){ fa.resize(n+1); sz.resize(n+1); for(int i=1;i<=n;i++){ fa[i]=i; sz[i]=1; } } int find(int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } bool merge(int x,int y){ int rx=find(x),ry=find(y); if(rx==ry){ return false; } if(sz[rx]>sz[ry]) swap(rx,ry); fa[rx]=ry; sz[ry]+=sz[rx]; return true; } }; void solve() { int n,m; cin >> n >> m; struct edge{ int u,v,w; }; vector<edge> e(m+1); for(int i=1;i<=m;i++){ cin >> e[i].u >> e[i].v >> e[i].w; } e[0].w=1e9; DSU dsu(n); ll ans=0; int cnt=0; bool change=true;//用于判断是否加了边，如果无法加边了，那么可能是最小生成森林 vector<int> mn(n+1);//记录每个连通块最小出边的编号 vector<bool> used(m+1,0);//判断每条边是否使用过 while(cnt<n-1&&change){ change=0; for(int i=1;i<=n;i++){ mn[i]=0; } for(int i=1;i<=m;i++){ auto[x,y,w]=e[i]; int rx=dsu.find(x),ry=dsu.find(y); if(rx==ry) continue; if(e[mn[rx]].w>w) mn[rx]=i; if(e[mn[ry]].w>w) mn[ry]=i; } for(int i=1;i<=n;i++){ int x=mn[i]; if(x&&!used[x]){ cnt++; ans+=e[x].w; dsu.merge(e[x].u,e[x].v); used[x]=1; change=1; } } } cout << ans << endl; } /* */ int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }时间复杂度为O ( α ( n ) m log n ) O(\alpha(n)m\log{n})O(α(n)mlogn)。
例题：
- J - Tree MST
- Problem - 888G - Codeforces
- E - Connecting Cities
- P2076 曼哈顿距离最小生成树 - 洛谷
下面我们先写一下例题2：https://codeforces.com/problemset/problem/888/G
题意：给了n nn个点，每个点的点权为a i a_iai，如果点i ii向点j jj连边，那么边权为a i ⊕ a j a_i\oplus a_jai⊕aj，问让所有点连通的最小代价。
sol
现在也就是给了( n 2 ) \binom{n}{2}(2n)条边，问最小生成树，显然对于这样的稠密图，我们无法使用Prim和Kruscal了，只能使用Boruvka算法。
我们按照算法步骤，可以知道难点在于求每个连通块的最小出边，假设现在我们连通块为S = { a 1 , a 2 , … , a k } S=\{a_1,a_2,\dots,a_k\}S={a1,a2,…,ak}，然后我们要知道S SS的最小出边，也就是求S SS中的点a i a_iai和S ‾ \overline SS中的点a j a_jaj的最小边权，因为边权w = a i ⊕ a j w=a_i\oplus a_jw=ai⊕aj，要求某一个点在一个集合中异或的最小值，这是经典的01trie维护，这里还有个技巧，求S ‾ \overline SS可以通过全集减去S SS得到，所以我们单独用r t [ 0 ] rt[0]rt[0]来表示所有数构成的01trie，那么S ‾ \overline SS可以表示为r t [ 0 ] − r t [ S ] rt[0]-rt[S]rt[0]−rt[S]得到。
所以具体步骤为：
- 初始化每个节点一个连通块，同时每个连通块维护一个
01trie； - 找到每个连通块的最小出边，我们的m n [ i ] mn[i]mn[i]存的是一个p a i r pairpair，第一个表示边权，第二个表示连向的点（因为01trie返回的也是一个节点编号）；
- 进行连边，合并
01trie，统计答案；
#include <bits/stdc++.h> using namespace std; #define endl '\n' using ll=long long; const int N=2e5+10; const int M=N*50; const ll inf=1e18; int fa[N],siz[N],n,a[N]; ll ans; pair<ll,int> mn[N]; int sz[M],tot,tail[M],rt[N],ch[M][2]; int find(int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } void insert(int& rt,int x,int idx){ if(!rt) rt=++tot; int now=rt; for(int i=29;i>=0;i--){ int p=x>>i&1; if(!ch[now][p]) ch[now][p]=++tot; now=ch[now][p]; ++sz[now]; } tail[now]=idx; } //v为全集，u为子集S，T为S的补集，查询x与T中的最小距离 //返回选的那个节点编号 int query(int u,int v,int x){ for(int i=29;i>=0;i--){ int p=x>>i&1; if((sz[ch[v][p]]-sz[ch[u][p]])>0){ u=ch[u][p]; v=ch[v][p]; }else{ u=ch[u][!p]; v=ch[v][!p]; } } return tail[v]; } //合并两个01trie，将u合并到v int mg(int u,int v){ if(!u||!v) return u|v; sz[v]+=sz[u]; ch[v][0]=mg(ch[v][0],ch[u][0]); ch[v][1]=mg(ch[v][1],ch[u][1]); return v; } //启发式合并 void merge(int u,int v){ u=find(u),v=find(v); if(siz[u]>siz[v]) swap(u,v); siz[v]+=siz[u]; fa[u]=v; rt[v]=mg(rt[u],rt[v]); } void solve(){ cin >> n; for(int i=1;i<=n;i++){ cin >> a[i]; } sort(a+1,a+1+n); n=unique(a+1,a+1+n)-a-1; for(int i=1;i<=n;i++){ siz[i]=1; fa[i]=i; insert(rt[i],a[i],i); insert(rt[0],a[i],i); } int cnt=0; while(cnt<n-1){ for(int i=1;i<=n;i++){ mn[i]={inf,0}; } for(int i=1;i<=n;i++){ int u=find(i); int v=query(rt[u],rt[0],a[i]); int w=a[i]^a[v]; if(mn[u].first>w){ mn[u]={w,v}; } } for(int i=1;i<=n;i++){ int x=find(i); if(x==i&&find(mn[x].second)!=x){ ans+=mn[x].first; merge(i,mn[x].second); cnt++; } } } cout << ans << endl; } /* */ int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }