Boruvka 算法简记

这个算法怕是只会存在于模拟赛里了。

Boruvka 算法是用于解决完全图的生成树的一类算法，因为完全图边数很多，因此普通时间复杂度基于边数的做法不适用。Boruvka 算法核心思想是 所有当前的连通块向其他连通块拓展出最小边，直到整张图只剩下一个连通块。

那么这个算法的核心部分非常简单，下面给出伪代码

while 连通块个数 > 1 :
    for 连通块 i :
        mi[i] = i 和 其他连通块连边的最小值
    for 连通块 i :
        if mi[i] 连接的不是同一个连通块 :
            ans += mi[i]
            合并两个连通块，连通块个数减 1

代码看上去非常简单，但是我们可以通过给 mi[i] 设限，因此使用该算法难点主要在考察如何求解 mi[i] 上。

这里给出例题

Xor-MST

给出 \(n\) 个点的完全图，每个点有一个点权 \(a_i\)，连接 \(i\) 号点和 \(j\) 号点的代价是 \(a_i\operatorname{xor} a_j\)。求这个图最小生成树的权值。

考虑怎样求 mi[i]，对于异或我们当然有两种方案，在本题，因为有合并和删除的关系，我们选择 Trie 树。

我们将所有的 \(a_i\) 建出一棵 Trie 树，将当前连通块 \(S'\) 的 Trie 树与整棵 Trie 树进行对比，设当前节点为 \(u\)，如果所有 \(a_i\) 的 Trie 树上，siz_u 比 \(S\) 的 Trie 树上的 siz_{S',u} 要大，那么说明向这边走肯定有一条连接两个不同的连通块的边。可以贪心选择。

#include <bits/stdc++.h>
#define il inline
#define pii pair<int, int>

using namespace std;

const int N = 2e5 + 5;
const int inf = 1061109567;
int a[N], n, mi[N], fa[N], lnk[N];

il int getfa(int u) { return fa[u] ^ u ? fa[u] = getfa(fa[u]) : fa[u]; }

int cnt, ch[N << 6][2], rt[N], son[N << 6], ed[N << 6];

il void insert(int p, int pos, int val)
{
    for (int i = 30; ~i; --i)
    {
        int c = (val >> i) & 1;
        ++son[p];
        if (!ch[p][c]) ch[p][c] = ++cnt;
        p = ch[p][c];
    }
    son[p] = 1;
    ed[p] = pos;
}

il void merge(int &x, int y)
{
    if (!x || !y) return x = x | y, void();
    merge(ch[x][0], ch[y][0]);
    merge(ch[x][1], ch[y][1]);
    son[x] = son[ch[x][0]] + son[ch[x][1]];
    ed[x] = ed[y];
}

il pii query(int all, int p, int val)
{
    int ans = 0;
    for (int i = 30; ~i; --i)
    {
        int c = (val >> i) & 1;
        if (son[ch[all][c]] - son[ch[p][c]] > 0)
            p = ch[p][c], all = ch[all][c];
        else
            ans = ans | (1 << i), p = ch[p][c ^ 1], all = ch[all][c ^ 1];
    }
    return make_pair(ans, ed[all]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], fa[i] = i;
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
    rt[0] = ++cnt;
    for (int i = 1; i <= n; ++i)
        insert(rt[0], i, a[i]), insert(rt[i] = ++cnt, i, a[i]);
    long long ans = 0;
    while (1)
    {
        memset(mi, 0x3f, sizeof mi);
        bool chg = false;
        for (int i = 1; i <= n; ++i)
        {
            int fx = getfa(i);
            pii tmp = query(rt[0], rt[fx], a[i]);
            int fy = getfa(tmp.second);
            if (fx != fy)
            {
                int z = tmp.first;
                if (z < mi[fx]) mi[fx] = z, lnk[fx] = fy;
                if (z < mi[fy]) mi[fy] = z, lnk[fy] = fx;
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            int fx = getfa(i), fy = getfa(lnk[i]);
            if (mi[i] < inf && fx != fy)
            {
                ans += mi[i], chg = true;
                merge(rt[fx], rt[fy]), fa[fy] = fx;
            }
        }
        if (!chg) break;
    }
    cout << ans << endl;
    return 0;
}

拿 clang-format 跑的格式化因为感觉自己的代码很丑（

可以仔细感受一下这个算法和贪心的妙处。