Dyd's Blog

He who has a strong enough why can bear almost any how.

Boruvka 最小生成树

Posted on In
Symbols count in article: 2.5k Reading time ≈ 2 mins.

另一种 MST

Boruvka 最小生成树

这种最小生成树常用于解决边很多，但边权又和点有关，并且常常和数据结构、 dp 、分治等套在一起

思路

  • 初始化每个点为一个联通块
  • 每一轮，对每个联通块找到权值最小的、连向其它联通块的边，加入 MST 并跟新联通性，直到只剩一个联通块

不难发现，每轮联通块数目至少会减少一半，所以最多进行 $\log n$ 轮，思想很简单，但“对每个联通块找到权值最小的、连向其它联通块的边”，这个操作给了我们乱搞的可能

例题

Xor-MST

$O(n^2)$ 级别的边数无法 kruskal ，考虑 Boruvka ，问题是如何找到每个联通块连向其它联通块的最小边，考虑 Trie ，对每个联通块建一棵 Trie ，再对全局建一棵 Trie ，维护好 size ，每次就在全局的 Tire 和当前联通块的 Tire 的差上找到最小边，这是 $O(n \log A)$ 的，然后合并联通块的同时合并 Trie 是 $O(n \log A)$ 的，加上 Boruvka ，总复杂度为 $O(n \log n \log A)$

注意到如果 $a$ 中有重复元素的话，可以不费代价的直接连起来，那么其实就只用考虑去重后的 $a$

似乎有更快的解法

代码如下：

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define fi first
#define se second
using LL = long long;
const int N = 2e5 + 100, inf = 0x3f3f3f3f;
int n, a[N], fa[N];
LL ans;
std::pair<int, int> mn[N];
struct Node
{
    int si, ed;
    Node *ch[2];
} pool[N * 60], *tot = pool, _null = {0, 0, {nullptr, nullptr}}, *null = &_null;
Node *rt[N], *tr;
int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); }
Node* _new(){ return *tot = {0, 0, {null, null}}, tot++; }
Node* merge(Node *x, Node *y)
{
    if (y == null) return x;
    if (x == null) return y;
    x->si += y->si;
    if (y->ed) x->ed = y->ed;
    x->ch[0] = merge(x->ch[0], y->ch[0]);
    x->ch[1] = merge(x->ch[1], y->ch[1]);
    return x;
}
void ins(Node *p, int x, int id)
{
    for (int i = 30, c; ~i; --i)
    {
        ++p->si;
        c = (x >> i) & 1;
        if (p->ch[c] == null) p->ch[c] = _new();
        p = p->ch[c];
    }
    ++p->si, p->ed = id;
}
int find(int id, int x)
{
    Node *p = rt[id], *q = tr;
    for (int i = 30, c, t; ~i; --i)
    {
        c = (x >> i) & 1;
        t = q->ch[c]->si - p->ch[c]->si;
        if (t <= 0) c ^= 1;
        q = q->ch[c];
        if (p->ch[c] != null) p = p->ch[c];
        else p = rt[0];
    }
    return q->ed;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    n = std::unique(a + 1, a + n + 1) - a - 1;
    std::iota(fa + 1, fa + n + 1, 1);
    tr = _new(), rt[0] = _new(); //建一个空节点用于find
    for (int i = 1; i <= n; ++i)
    {
        rt[i] = _new();
        ins(rt[i], a[i], i), ins(tr, a[i], i);
    }
    for (int o = n - 1; o; )
    {
        for (int i = 1; i <= n; ++i) mn[i] = {inf, inf};
        for (int i = 1, t, t1, t2; i <= n; ++i)
        {
            t2 = find(t = get(i), a[i]);
            t1 = a[i] ^ a[t2];
            mn[t] = std::min(mn[t], {t1, t2});
        }
        for (int i = 1, j, k; i <= n && o; ++i) if (mn[i].fi < inf)
        {
            k = get(i), j = get(mn[i].se); 
            if (k == j) continue;
            ans += mn[i].fi;
            fa[j] = k, rt[k] = merge(rt[k], rt[j]);
            --o;
        }
    }
    printf("%lld\n", ans);
    return 0;
}