CF888G Xor-MST

原题链接：G. Xor-MST

Tag：图论、MST、Trie

题目描述

给定一个具有 \(n\) 个结点的完全无向图，每个点给定点权 \(a_i\)，连接 \(i\) 与 \(j\) 的代价为 \(a_i \oplus a_j\)。

求这个图的最小生成树的权值。

数据说明： \(1 \leq n \leq 2 \times 10^5，0 \leq a_i \lt 2^{30}。\)

分析

解法1

首先看到题要求 \(\text{MST}\)，可以想到或许要使用一种 \(\text{MST}\) 的算法。

之后看数据范围，发现范围是 \(2e5\) 的，并且题目给出的图是一个完全图，结合边的代价为 \(a_i \oplus a_j\) 这一点，如果我们在求 \(\text{MST}\) 的时候遍历了所有的边，复杂度显然是不可接受的。所以我们需要使用一种方法来优化选边的过程，发现求最小代价的边的本质是一种最小异或对，因此我们可以使用 \(\text{01Trie}\) 来寻找可以连接的边。

我们考虑一下找边时候的异或计算，异或的本质是二进制下不进位的加法，因此我们可以把位拆开考虑。根据异或运算，尝试把每一位按照是 \(0\) 还是 \(1\) 分成两组，会发现这一位在 \(0\) 和 \(1\) 两组内分别内部连边无疑是最优的，因为这一位上没有产出额外的代价。对于两边的点我们可以继续看更低位，再尝试把更低位按照是 \(0\) 还是 \(1\) 分成两组 \(\cdots\) 。

对于上述这一段，必须要说清楚的是，这里的按照是 \(0\) 还是 \(1\) 分组是对于递归到的区间来说的，递归到的区间保证了这些数字的高一位到最高位完全相同。

不难发现从这里开始我们进入了一个递归的过程，我们考虑按位分组递归。「递」的过程是我们把每一位按照是 \(0\) 还是 \(1\) 分成两组，我们考虑一下「归」的时候要怎么进行左右两组的连边，其实我们在「归」的时候左部分和右部分他们之间已经分别组成了连通块，所以我们只需要找一条边让当前的左部分和右部分连起来就可以了，因此我们这里在实现的时候可以把左部分插入到 \(\text{01Trie}\) 上，之后在右部分遍历在 \(\text{01Trie}\) 上去查找最小的异或对就可以了。

这里的本质十分接近归并。

上述做法在递归时因有 \(logV\) 的复杂度因为有 \(logV\) 层，每一层对于 \(\text{01Trie}\) 的处理是 \(nlogV\)的，因此复杂度为 \(O(n\log^{2}V)\)。

除此之外，上述做法的本质其实是类 \(\text{Kruskal}\)，因为我们保证了连边的时候从消耗最小的边开始连。

代码实现

解法1

struct Trie01 {
    static const int StrMaxLen = 2e5 + 5;//数字个数
    static const int SigmaSize = 31;//int开31 ll开63
    int trie[StrMaxLen * SigmaSize][2], idx = 0;
    void init(){
        for (int i = 0; i <= idx ; ++i) {
            trie[i][0] = trie[i][1] = 0;
        }
        idx = 0;
    }
    void insert(int x) {
        int cur = 0;
        for (int i = 30; i >= 0; i--) {
            int j = x >> i & 1;
            if (!trie[cur][j]) trie[cur][j] = ++idx;
            cur = trie[cur][j];
        }
    }
    int queryMinXorWithX(int x){
        int cur = 0, ans = 0;
        for (int i = 30; i >= 0; i--) {
            int j = x >> i & 1;
            if (trie[cur][j]) {
                cur = trie[cur][j];
            } else {
                ans += 1 << i;
                cur = trie[cur][!j];
            }
        }
        return ans;
    }
};
Trie01 trie;
void NeverSayNever() {
    int n;
    cin >> n;
    vector<int> val(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
    }
    std::sort(val.begin(), val.end());
    auto dfs = [&](auto &&self, int l, int r, int dep) -> int {
        if (dep < 0 || l >= r) return 0;
        int mid = l - 1;
        while (mid + 1 <= r && (val[mid + 1] >> dep & 1) == 0) {
            mid++;
        }
        if (mid == l - 1 || mid == r) {
            return self(self, l, r, dep - 1);
        }
        int ans = LLONG_MAX;
        trie.init();
        for (int i = l; i <= mid; ++i) {
            trie.insert(val[i]);
        }
        for (int i = mid + 1; i <= r; ++i) {
            ans = min(ans, trie.queryMinXorWithX(val[i]));
        }
        ans += self(self, l, mid, dep - 1) + self(self, mid + 1, r, dep - 1);
        return ans;
    };
    cout << dfs(dfs, 1, n, 30) << endl;
}

日志

本页面创建于 2024/09/01 13:24

特别鸣谢：

Ackerlanna的耐心指点。

UPD-1：2024/09/01 13:36

在Jlyfish的指正下更正若干笔误。