题意

给定 n 个点的完全图,边 (i,j) 的边权定义为 a_i\oplus a_j,求最小生成树。

即最小异或生成树模板

题解

考虑 Boruvka 算法,每次合并两个连通块,这样合并次数就是 O(\log n) 级别的。由于要使异或的结果尽量小,所以考虑对于每一位分治。按照第 i 位为 01 分为两个集合,易知两个集合间只连一条边是最优的,然后对于这两个集合继续分治,递归处理即可。

两集合之间的连边使用 0-1 Trie 寻找异或最小值即可,详见代码。

#include <cstdio>
#include <cctype>
#include <vector>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

typedef long long ll;
const int maxn = 2e5 + 5;

int read()
{
    int s = 0, x = 0;
    char c = getchar();
    while (!isdigit(c))
        x |= (c == '-'), c = getchar();
    while (isdigit(c))
        s = s * 10 + c - '0', c = getchar();
    return x ? -s : s;
}

inline ll min(ll a, ll b) {return a < b ? a : b;}

int n;

int ch[maxn * 32][2], tot;
ll ans = 0;

void insert(int x)
{
    int p = 0;
    DEC(i, 30, 0)
    {
        int tmp = (x >> i) & 1;
        if (!ch[p][tmp])
            ch[p][tmp] = ++tot, ch[tot][0] = ch[tot][1] = 0;
        p = ch[p][tmp];
    }
    return;
}

int query(int x)
{
    int p = 0, ret = 0;
    DEC(i, 30, 0)
    {
        int tmp = (x >> i) & 1;
        if (ch[p][tmp]) p = ch[p][tmp];
        else if (ch[p][tmp ^ 1]) p = ch[p][tmp ^ 1], ret += (1 << i);
        else break;
    }
    return ret;
}

ll work(std::vector<int> a, int dep)
{
    if (dep < 0 || a.empty()) return 0;
    std::vector<int> b[2];
    ll ret = 0;
    FOR(i, 0, a.size() - 1) b[(a[i] >> dep) & 1].push_back(a[i]);//按照该位 0/1 分类
    if (b[0].size() && b[1].size())
    {
        tot = ch[0][0] = ch[0][1] = 0;
        ret = 1e9;
        FOR(i, 0, b[0].size() - 1)
            insert(b[0][i]);
        FOR(i, 0, b[1].size() - 1)
            ret = min(ret, query(b[1][i]));
    }
    return ret + work(b[0], dep - 1) + work(b[1], dep - 1);
}

int main()
{
    n = read();
    std::vector<int> a;
    FOR(i, 1, n) a.push_back(read());
    printf("%lld\n", work(a, 30));
    return 0;
}
最后修改日期: 2021年3月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。