学习笔记 - Boruvka 生成树算法 | Lucky_Glass's Blog
0%

学习笔记 - Boruvka 生成树算法

Boruvka 算法可谓 Prim 算法和 Kruskal 算法的结合体……


Part1. 初识 Boruvka

对于生成树算法,我们最先想到的是 ① 从最小边开始加边的 Kruskal、② 从当前构造出的树向外扩展的 Prim ……

而 Boruvka 算法是两者的结合体,可能因为这个算法太像 Kruskal 和 Prim 了……它一直比较冷门。但是,用到这个算法的好题也不少。总而言之还是学一下好了。

Boruvka 算法的一句话思想便是:

“从所有当前的连通块向其他连通块扩展出最小边,直到只剩一个连通块”,其中取最小边的贪心思想是 Kruskal 的主体,而向外扩展又是 Prim 的思想 —— 基于另外两种生成树算法,Boruvka 的正确性显然。


Part2. Boruvka 的实现

其实代码框架非常浅显易懂:

1
2
3
4
5
6
7
8
while 连通块个数>1
for 每个连通块 i
mn[i] = 连接 i 与其他连通块的最小边
for 每个连通块 i
if mn[i] 连接两个不同的连通块
ans += mn[i]
Merge( mn[i] 连接的连通块 )
连通块个数 --

其中最为重要的是求 mn[i],可能会以其他各种算法辅助求解,这也是出题人设题的主要考察点。

由于每进行一次操作,连通块个数会减少一半,因此(如果记 $O(T)$ 是计算 mn[] 的复杂度)这个算法的复杂度是 $O(T\log_2N)$。最朴素的求 mn[] 的方法是 $O(M)$ 枚举边,如果可以优化这一步骤,效率会大大提高。

>> 个人看法

考察 Boruvka 算法的题目大多数会在求解 mn[] 这里设置难度,比如让边数超级大……因此很多的题目都是“给出一种计算两点之间边权的方式,求一个完全图的生成树”。

这样的话 $O(M)$ 即 $O(N^2)$,大多数题目是过不了的……


Part3. 例题 - XOR MST (CF 888G)

下面让我们来看看一道非常好的例题(别的算法的版子题都非常水,唯有 Boruvka 极其恶心……)

Part3/1. 题面

有 n 个点构成一个完全图,每个点的点权为 $a_i$,连接 i,j 的边的权值为 $a_i\oplus a_j$ (异或)。求最小生成树。

$1\le n\le2\times10^5,0\le a_i\le2^{30}$

Part3/2. 解析

你看它是一个完全图……非常适合 Boruvka,于是就想怎么求 mn[]。也就是说对于一个连通块 S,求 $i\in S,j\not\in S$ 的 $a_i\oplus a_j$ 的最小值。

对于异或最小值,我们有两种常见的处理方法 —— 线性基、字典树。然而在合并两个连通块的时候,如果用线性基,不止要合并两个连通块的线性基,还要从不属于该连通块的线性基中删除……(线性基不支持删除,但是字典树可以)

于是考虑先建出所有 $a_i$ 的字典树。当我们询问连通块 S 的 mn[S] 时,将 $a_i (i\in S)$ 在字典树中删掉,然后对于每个 $a_i$ ($i\in S$) 在字典树里贪心地求一个异或最小值,更新 mn[S]。计算完 mn[S] 后,再把 $a_i$ $(i\in S)$ 重新插入字典树。

一次字典树的操作是 $O(\log_2 a_i)$ 的,每次求 mn[] 时会遍历所有 $n$ 个点一次(因为每个点都属于恰好一个连通块)。因此求一次 mn[] 是 $O(n\log_2 a_i)$ 的。套上 Boruvka 的复杂度,总体复杂度就是 $O(n\log_2 n\log_2a_i)$(小心卡常)。

Part3/3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5;

int n;
int A[N+3],idmap[N+3],mnval[N+3],mnto[N+3];
vector<int> blg[N+3];

struct DSU{
int fa[N+3];
int FindFa(int u){
if(u==fa[u]) return u;
return fa[u]=FindFa(fa[u]);
}
bool Merge(int u,int v){
int fu=FindFa(u),fv=FindFa(v);
if(fu==fv) return false;
fa[fu]=fv;
return true;
}
void Init(){
for(int i=1;i<=n;i++)
fa[i]=i;
}
}D;
struct NODE{
int siz,id;
NODE *ch[2];
};
struct TRIE{
NODE pol[N*35],*root,*ncnt,*NIL;
void Init(){
ncnt=NIL=root=pol;
NIL->ch[0]=NIL->ch[1]=NIL;
NIL->siz=NIL->id=0;
}
NODE *NewNode(){
NODE *p=++ncnt;
*p=*NIL;
return p;
}
void Modify(NODE *&u,int num,int dep,int val,int id){
if(u==NIL) u=NewNode();
u->siz+=val;
if(dep<0){
u->id=id;
return;
}
int dir=bool(num&(1<<dep));
Modify(u->ch[dir],num,dep-1,val,id);
}
int Query(NODE *u,int num,int dep){
if(dep<0) return u->id;
int dir=bool(num&(1<<dep));
if(u->ch[dir]->siz) return Query(u->ch[dir],num,dep-1);
return Query(u->ch[!dir],num,dep-1);
}
}T;

int main(){
scanf("%d",&n);
T.Init();D.Init();
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
sort(A+1,A+1+n);
A[0]=-1;
for(int i=1;i<=n;i++){
T.Modify(T.root,A[i],29,1,i);
if(A[i]==A[i-1])
D.Merge(i,i-1);
}
long long ans=0;
while(true){
int cnt=0;
for(int i=1;i<=n;i++)
if(D.fa[i]==i){
idmap[i]=++cnt;
mnto[cnt]=-1;
mnval[cnt]=-1;
}
if(cnt==1) break;
for(int i=1;i<=n;i++)
blg[idmap[D.FindFa(i)]].push_back(i);
for(int i=1;i<=cnt;i++){
for(int j=0;j<(int)blg[i].size();j++){
int u=blg[i][j];
T.Modify(T.root,A[u],29,-1,u);
}
for(int j=0;j<(int)blg[i].size();j++){
int u=blg[i][j];
int resu=T.Query(T.root,A[u],29);
if(mnval[i]==-1 || mnval[i]>(A[u]^A[resu])){
mnval[i]=(A[u]^A[resu]);
mnto[i]=resu;
}
}
for(int j=0;j<(int)blg[i].size();j++){
int u=blg[i][j];
T.Modify(T.root,A[u],29,1,u);
}
blg[i].clear();
}
for(int i=1;i<=n;i++)
if(D.fa[i]==i && D.Merge(i,mnto[idmap[i]]))
ans+=mnval[idmap[i]];
}
printf("%lld\n",ans);
return 0;
}

The End

Thanks for reading!

你已经理解了 Boruvka 了?