一种另类的最小生成树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 lllong long; struct DSU{ int n; vectorint fa,sz; DSU(int n):n(n){ fa.resize(n1); sz.resize(n1); for(int i1;in;i){ fa[i]i; sz[i]1; } } int find(int x){ if(xfa[x]) return x; else return fa[x]find(fa[x]); } bool merge(int x,int y){ int rxfind(x),ryfind(y); if(rxry){ 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; }; vectoredge e(m1); for(int i1;im;i){ cin e[i].u e[i].v e[i].w; } e[0].w1e9; DSU dsu(n); ll ans0; int cnt0; bool changetrue;//用于判断是否加了边如果无法加边了那么可能是最小生成森林 vectorint mn(n1);//记录每个连通块最小出边的编号 vectorbool used(m1,0);//判断每条边是否使用过 while(cntn-1change){ change0; for(int i1;in;i){ mn[i]0; } for(int i1;im;i){ auto[x,y,w]e[i]; int rxdsu.find(x),rydsu.find(y); if(rxry) continue; if(e[mn[rx]].ww) mn[rx]i; if(e[mn[ry]].ww) mn[ry]i; } for(int i1;in;i){ int xmn[i]; if(x!used[x]){ cnt; anse[x].w; dsu.merge(e[x].u,e[x].v); used[x]1; change1; } } } 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 MSTProblem - 888G - CodeforcesE - Connecting CitiesP2076 曼哈顿距离最小生成树 - 洛谷下面我们先写一下例题2https://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 wa_i\oplus a_jwai​⊕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 lllong long; const int N2e510; const int MN*50; const ll inf1e18; int fa[N],siz[N],n,a[N]; ll ans; pairll,int mn[N]; int sz[M],tot,tail[M],rt[N],ch[M][2]; int find(int x){ if(xfa[x]) return x; else return fa[x]find(fa[x]); } void insert(int rt,int x,int idx){ if(!rt) rttot; int nowrt; for(int i29;i0;i--){ int pxi1; if(!ch[now][p]) ch[now][p]tot; nowch[now][p]; sz[now]; } tail[now]idx; } //v为全集u为子集ST为S的补集查询x与T中的最小距离 //返回选的那个节点编号 int query(int u,int v,int x){ for(int i29;i0;i--){ int pxi1; if((sz[ch[v][p]]-sz[ch[u][p]])0){ uch[u][p]; vch[v][p]; }else{ uch[u][!p]; vch[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){ ufind(u),vfind(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 i1;in;i){ cin a[i]; } sort(a1,a1n); nunique(a1,a1n)-a-1; for(int i1;in;i){ siz[i]1; fa[i]i; insert(rt[i],a[i],i); insert(rt[0],a[i],i); } int cnt0; while(cntn-1){ for(int i1;in;i){ mn[i]{inf,0}; } for(int i1;in;i){ int ufind(i); int vquery(rt[u],rt[0],a[i]); int wa[i]^a[v]; if(mn[u].firstw){ mn[u]{w,v}; } } for(int i1;in;i){ int xfind(i); if(xifind(mn[x].second)!x){ ansmn[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; }