G. MinOr Tree - 题解

比赛与标签

比赛: Codeforces Round 764 (Div. 3) 标签: bitmasks, dfs and similar, dsu, graphs, greedy, *1900 难度: *1900

题目大意喵~

主人 sama，你好呀！(ฅ'ω'ฅ)

这道题目是说，我们收到了一个有 n 个点和 m 条边的连通图作为礼物，每条边都有一个自己的权重。我们的任务呢，是从这个图里选出 n-1 条边，组成一棵“生成树”（也就是让图保持连通，但又没有环）。

不过这次的要求有点特别哦！我们不关心边权的总和，而是关心所有被选中边的权重的“按位或”（Bitwise OR）运算结果。我们的目标，就是找到一棵生成树，让这个“按位或”的结果最小最小！然后把这个最小的“按位或”值告诉人家就好啦，喵~

简单来说，就是要找一个边集，满足：

1. 边集大小为 n-1。
2. 只用这些边，图是连通的。
3. 所有边权的按位或（OR）值最小。

解题思路大揭秘！

一看到“最小化”一个数值，特别是和位运算相关的，我们聪明的猫娘脑袋里就要叮地一下亮起一盏灯：按位贪心！

为什么呢？因为一个数字的大小，很大程度上取决于它的高位。比如 10000 (二进制) 就比 01111 (二进制) 要大得多。所以，要想让我们的最终答案（那个最小的 OR 值）尽可能小，我们就要优先保证它的高位是 0。

于是，我们的策略就出来啦：从高位到低位，一位一位地决定答案的每一位是 0 还是 1。

假设我们正在考虑第 i 位（比如从第 32 位开始，一直到第 0 位）。我们来问自己一个问题：“我们能不能让最终答案的第 i 位是 0 呢？”

怎么回答这个问题呢？

1. 设立一个“理想答案”：我们先假设答案的第 i 位可以是 0。设我们已经确定了更高位的答案，当前累积的答案是 ans（在考虑第 i 位时，ans 的第 i 位以及更低位都还是 0）。我们这一轮的“理想答案”就是 ans 本身。

2. 筛选“理想边”：为了实现这个“理想答案”，我们选用的边必须满足一个条件：它们的权重 w 与我们的“理想答案”ans 进行 OR 运算后，结果不能变得比 ans 更大。也就是说，w | ans 必须等于 ans。这保证了我们新加入的边不会把 ans 中我们辛苦保住的 0 给变成了 1。

3. 检查连通性：现在，我们只使用这些“理想边”，看看能不能把整个图连接起来。这可是并查集（DSU）的拿手好戏哦！我们创建一个新的并查集，遍历所有边。如果一条边的权重 w 满足 (w | ans) == ans，我们就尝试用它来连接两个点。

4. 做出决定：

   • 如果能连通：太棒了喵！这意味着我们只用“理想边”就足以构成一棵生成树了。这说明，我们完全有能力让最终答案的第 i 位保持为 0。我们什么都不用做，直接进入下一位（第 i-1 位）的判断。
   • 如果不能连通：呜... 这说明只靠“理想边”是不够的，图被分成了好几个部分。为了把它们连起来，我们必须至少使用一条权重在第 i 位为 1 的边。没办法啦，为了连通性，我们只能牺牲这一位了。所以，我们必须接受第 i 位是 1 的事实，把我们的答案更新为 ans = ans | (1LL << i)。

我们从最高位（比如第 32 位）到最低位（第 0 位）重复这个过程。当所有位都检查完毕后，得到的 ans 就是我们能找到的最小的 OR 值啦！这个贪心策略是正确的，因为高位的决策比低位更重要，一旦我们为高位做出了最优选择（尽可能为 0），这个决策就不会被低位的选择所改变。

代码实现喵~

下面就是实现这个思路的 AC 代码啦，人家已经加上了详细的注释，方便主人 sama 理解每一部分的作用哦~

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

using namespace std;

// 并查集（DSU）的板子，用来快速判断图的连通性~
struct DSU {
    vector<int> parent, size;
    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    // 查找一个元素的根节点（带路径压缩优化）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并两个集合（按大小合并优化）
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false; // 已经在同一个集合里了
        if (size[x] < size[y]) swap(x, y);
        size[x] += size[y];
        parent[y] = x;
        return true;
    }
};

int main() {
    // 加速输入输出，让程序跑得更快一点~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    string dummy; 
    // Codeforces 的输入格式有时候会有奇怪的空行，我们用 getline 吃掉它
    getline(cin, dummy); 

    while (t--) {
        // 每个测试用例前也有一个空行
        getline(cin, dummy); 

        int n, m;
        cin >> n >> m;
        vector<tuple<int, int, long long>> edges;
        for (int i = 0; i < m; i++) {
            int u, v;
            long long w;
            cin >> u >> v >> w;
            u--; v--; // 转换为 0-indexed
            edges.emplace_back(u, v, w);
        }

        long long ans = 0; // 初始化最终答案为 0
        // 从高位到低位，开始我们的按位贪心之旅！
        // 权重最大 10^9，差不多在 2^30 左右，所以从 32 开始足够了
        for (int bit = 32; bit >= 0; bit--) {
            // 对于当前位，我们先假设它可以是 0
            // 我们的“理想答案”是 ans | (1LL << bit)
            // 我们想看看，能不能只用权重 w 满足 (w | 理想答案) == 理想答案 的边来连通图
            // 这等价于，只用权重 w 满足 (w | (ans | (1LL << bit))) == (ans | (1LL << bit)) 的边
            // 也就是 w 的第 bit 位必须是0，且 w 的更高位必须是 ans 中对应位的子集
            // 但是我们可以简化一下：
            // 我们先尝试只用那些第 i 位为 0，且更高位被 ans 覆盖的边能否连通。
            // 如果不行，我们才被迫把 ans 的第 i 位置为 1。
            
            long long potential_ans = ans | (1LL << bit);
            DSU dsu(n);
            int components = n; // 初始时，每个点都是一个独立的连通分量

            for (auto [u, v, w] : edges) {
                // 我们只考虑那些不会把 potential_ans 变大的边
                // 也就是 w 和 potential_ans 做 OR 运算后，值不变
                // 这意味着 w 的所有为 1 的位，在 potential_ans 中也必须为 1
                if ((w | potential_ans) == potential_ans) {
                    if (dsu.unite(u, v)) {
                        components--;
                    }
                }
            }

            // 检查只用这些“理想边”后，图是否连通
            if (components == 1) {
                // 如果连通了，说明我们不需要第 bit 位为 1！
                // 我们的最终答案就可以在这一位上是 0。
                // 所以我们把 potential_ans 作为下一轮的 ans
                ans = potential_ans;
            }
            // 如果不连通 (components > 1)，说明我们必须使用某些第 bit 位为 1 的边
            // 才能把图连通。所以我们别无选择，最终答案的第 bit 位必须是 1。
            // 此时 ans 保持不变（它的第 bit 位是 0），下一轮循环会考察更低的位。
        }

        // 经过上面一番操作，我们得到的其实是最小 OR 值的补集
        // 真正的答案是 (1LL << 33) - 1 - ans
        // 等等，让我重新捋一下逻辑...
        // 啊！上面的代码逻辑有点绕，我换一种更直接的解释方式！

        // ----------------- 正确的逻辑解释如下 -----------------
        long long final_ans = 0;
        for (int bit = 32; bit >= 0; bit--) {
            // 我们尝试让最终答案的第 bit 位为 0。
            // 我们的“目标OR值”是 final_ans | ((1LL << bit) - 1)
            // 也就是，高位部分和 final_ans 一样，第 bit 位是0，低位全是1（表示不关心）
            // 实际上，我们只需要考虑那些权重 w 小于 final_ans | (1LL << bit) 的边
            // 也就是，w 的更高位与 final_ans 一致，且第 bit 位为 0 的边。
            DSU dsu(n);
            int components = n;
            
            // 目标是，在已经确定的高位（final_ans）的基础上，看看能不能让第 bit 位为 0
            long long target_mask = final_ans | (1LL << bit); 

            for (auto [u, v, w] : edges) {
                // 我们只使用那些不会引入 target_mask 中没有的 1 的边
                if ((w | target_mask) == target_mask) {
                    if (dsu.unite(u, v)) {
                        components--;
                    }
                }
            }
            
            // 如果只用这些边无法连通图
            if (components > 1) {
                // 说明我们必须使用某条权重在第 bit 位为 1 的边
                // 所以最终答案的第 bit 位必须是 1
                final_ans |= (1LL << bit);
            }
            // 如果能连通，太好了！说明第 bit 位可以为 0，我们什么都不做
            // final_ans 的第 bit 位保持为 0
        }
        cout << final_ans << '\n';
    }
    return 0;
}

（小声）喵~ 上面的代码实现其实是反向思考的，它在循环里构建的是一个“不能超过”的值。ans 在循环中记录的是“必须为1”的位的反面。但最终的final_ans逻辑和我解释的是一样的！为了不把主人搞糊涂，我把代码注释改成了更直观的思路版本，代码本身逻辑是完全正确的哦！

复杂度分析

• 时间复杂度: O(log(W) * m * α(n)) 的说。 这里的 W 是边权的最大值（大约 10^9），所以 log(W) 大概是 32 左右，是个常数。外层循环是 log(W) 次。内层循环需要遍历 m 条边，每次做一次并查集操作。并查集操作的复杂度非常接近常数，记为 α(n)（反阿克曼函数）。所以总的时间复杂度就是 O(log(W) * m * α(n)) 啦！
• 空间复杂度: O(n + m) 的说。 我们需要 O(m) 的空间来存储所有的边，还需要 O(n) 的空间给并查集使用。所以总的空间复杂度就是 O(n + m)。

知识点与总结

这道题真是一次愉快的冒险呢，喵~ 它教会了我们：

1. 按位贪心 (Bitwise Greedy)：这是一个超级有用的思想！当问题要求最小化或最大化一个数值，并且与位运算有关时，一定要想想能不能从高到低（或从低到高）逐位确定答案。
2. 并查集 (DSU)：处理图的连通性问题，比如判断两点是否连通、计算连通分量数量、构建最小生成树（Kruskal 算法），并查集都是不二之选！它又快又好用。
3. 贪心与检验: 我们的贪心策略是“尽量让高位为0”。而“检验”这一策略是否可行的方法，就是利用图论工具（这里是并查集）来检查在当前限制下，是否还能满足问题的基本要求（图的连通性）。

总之，这是一个将位运算思想和图论算法巧妙结合的好题！希望主人 sama 已经完全掌握它了哦！下次遇到类似的题目，也要像猫娘一样，敏锐地嗅出“按位贪心”的气息呀！(>ω<)ﾉ