maximum clique 1 - 题解

标签与难度

标签: 图论, 二分图, 最大匹配, 最大独立集, 位运算, Kőnig定理, 建模 难度: 2100

题目大意喵~

主人你好呀，喵~ 这道题是这样子的：

我们有一个包含 n 个不同正整数的集合 S。我们的任务是从 S 中选出一个子集，这个子集要尽可能地大，并且满足一个特殊的条件：子集里任意两个数的二进制表示，都必须至少有两位不相同！

最后，我们要输出这个最大子集的大小，以及其中包含的所有数字，喵~

举个栗子：如果集合是 {3, 5, 6}。

• 3 的二进制是 011
• 5 的二进制是 101
• 6 的二进制是 110

3(011) 和 5(101) 有两位不同（第一位和第二位），可以共存。 3(011) 和 6(110) 有三位不同，可以共存。 5(101) 和 6(110) 只有一位不同（第三位），所以它们不能同时被选中！

所以，我们可以选 {3, 5} 或者 {3, 6}，但不能选 {3, 5, 6}。最大的子集大小是 2，比如 {3, 5}。

解题思路分析

这道题看起来是在集合里挑数字，但其实呀，它是一只伪装成数字题的图论小怪兽哦，喵！让我来揭开它的真面目吧！

步骤一：把问题“翻译”成图论语言

题目的核心要求是：“任意两个数，二进制位至少有 2 位不同”。

我们换个角度想，什么情况下两个数不能共存呢？ 因为题目说了所有数都不同，所以它们至少有 1 位不同。那么，不能共存的条件就是“二进制位恰好只有 1 位不同”。

这听起来就像是图里的“边”一样，对吧？我们可以把每个数字看作一个节点。如果两个数字 u 和 v 的二进制表示恰好只有 1 位不同，我们就在它们之间连一条边。这条边就代表着“u 和 v 不能同时被选择”。

这样一来，问题就变成了：

在这个新构建的图 G 中，找到一个最大的节点子集，使得子集中的任意两个节点之间都没有边直接相连。

这不就是图论中经典的 最大独立集 (Maximum Independent Set) 问题嘛！喵哈哈，抓住你了！

步骤二：发现图的“隐藏特性”——二分图

最大独立集问题在普通图上是 NP-hard 的，非常难解，直接暴力搜索肯定会超时的说。但是，我们这个图可能有什么特殊的性质呢？

我们来看看边的条件：两个数 u 和 v 之间有边，当且仅当它们二进制差一位。 一个数改变一个二进制位（从0到1，或从1到0），它二进制表示中 1 的个数（也就是 popcount）的奇偶性一定会改变！

• 如果 popcount(u) 是奇数，那么与它只差一位的 v 的 popcount(v) 一定是偶数。
• 如果 popcount(u) 是偶数，那么与它只差一位的 v 的 popcount(v) 一定是奇数。

这意味着，我们图里的每一条边，都连接着一个“1的个数为奇数”的节点和一个“1的个数为偶数”的节点。

这正是二分图的定义呀！我们可以把所有的节点分成两个集合：

• L 部：所有 popcount 为奇数的数字。
• R 部：所有 popcount 为偶数的数字。

图中的所有边都只会出现在 L 部和 R 部之间，L 部内部、R 部内部绝对不会有边，完美！

步骤三：利用 Kőnig 定理求解

对于二分图，有一个超级好用的定理叫做 Kőnig 定理，它告诉我们一个秘密关系：

在任意二分图中，最小顶点覆盖 的大小 等于 最大匹配 的大小。 |最小顶点覆盖| = |最大匹配|

这又是什么意思呢？

• 最大匹配：在一个图里选出尽可能多的边，使得这些边两两之间没有公共顶点。可以想象成在 L 部和 R 部之间牵红线配对，让尽可能多的人配上对，但每个人只能有一根红线。
• 最小顶点覆盖：选出最少的点，使得图中的每一条边都至少有一个端点被选中。

还有一个更通用的图论定理：

对于任意图，最大独立集 的大小 加上 最小顶点覆盖 的大小 等于 图的总顶点数。 |最大独立集| + |最小顶点覆盖| = |V|

把这两个公式合在一起，我们就得到了解决这道题的钥匙！ |最大独立集| = |V| - |最小顶点覆盖| = |V| - |最大匹配|

这里的 |V| 就是总的数字个数 n。所以，我们只要算出这个二分图的最大匹配数 M，那么答案的大小就是 n - M 啦！

步骤四：寻找最大匹配和最大独立集本身

1. 求最大匹配：我们可以用经典的匈牙利算法（或者说，基于 DFS 的增广路算法）来求二分图的最大匹配。我们从 L 部的每个节点出发，尝试为它寻找一个 R 部的匹配对象。如果 R 部的对象已经被别人匹配了，我们就尝试给那个“别人”另找一个对象（递归进行），看能不能腾出位置来。这个过程就像是为单身的朋友们不断牵线、调整，直到无法再增加新的配对为止，喵~

2. 找出最大独立集的成员：光知道大小还不够，我们还要把这些数字找出来。这就要用到从最大匹配结果构造最小顶点覆盖，再取其补集的方法了。

   • 一个标准的构造方法是：从 L 部所有未匹配的节点出发，进行一次特殊的 DFS/BFS 遍历。
   • 遍历规则是：从 L 部到 R 部只能走非匹配边，从 R 部到 L 部只能走匹配边。
   • 遍历结束后，所有被访问到的节点构成一个集合 Visited。
   • 最小顶点覆盖 = (L 部中未被访问的节点) ∪ (R 部中被访问到的节点)。
   • 最大独立集 = (L 部中被访问到的节点) ∪ (R 部中未被访问到的节点)。

这样，我们就能完美地解决这个问题啦！

代码实现

这是我根据上面的思路，精心重构的一份代码哦！注释超详细的，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

// 使用 C++20 的 popcount，如果编译器不支持，可以手写或用 __builtin_popcount
#if __cplusplus >= 202002L
#include <bit>
#endif

// 用于存储每个数字和它在原始输入中的信息
struct NumberInfo {
    int value; // 数字的值
    int original_index; // 原始索引，用于在邻接表中表示节点
};

// 邻接表来表示二分图
std::vector<int> adj[5005];
// match[i] 存储与节点 i 匹配的节点
int match[5005];
// visited 数组用于每次 DFS 寻找增广路时标记节点
bool visited[5005];

// 检查 x 是否是 2 的幂（即只有一个 bit 是 1）
// 两个数异或结果是 2 的幂，说明它们只差一个 bit
bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

// C++17 及以下版本的 popcount 实现
#ifndef __cpp_lib_bitops
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}
#endif

// 匈牙利算法的核心：通过 DFS 寻找增广路
bool dfs_match(int u) {
    // u 是 L 部的一个节点
    for (int v : adj[u]) {
        // v 是 R 部的一个邻居节点
        if (!visited[v]) {
            visited[v] = true;
            // 如果 v 未被匹配，或者 v 的匹配对象可以找到新的匹配
            if (match[v] == 0 || dfs_match(match[v])) {
                match[v] = u; // 将 u 和 v 匹配
                return true;  // 成功找到一条增广路
            }
        }
    }
    return false; // 未能为 u 找到匹配
}

// 用于寻找最大独立集的特殊遍历
void find_mis_nodes(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        // 从 L 到 R 走非匹配边，且 R 侧的 v 未被访问过
        // match[v] != u 确保是条非匹配边
        // match[v] != 0 确保 R 侧 v 的匹配对象存在且不是 u
        // !visited[match[v]] 确保 v 的匹配对象尚未访问，避免死循环
        if (match[v] != u && !visited[v]) {
            visited[v] = true;
            // 从 R 到 L 必须走匹配边
            if (match[v] != 0 && !visited[match[v]]) {
                find_mis_nodes(match[v]);
            }
        }
    }
}


int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<NumberInfo> all_nums(n);
    std::vector<NumberInfo> L_partition, R_partition;
    // 使用 map 快速查找数值对应的图节点编号
    std::map<int, int> value_to_node_idx;

    for (int i = 0; i < n; ++i) {
        all_nums[i].original_index = i + 1; // 节点编号从 1 开始
        std::cin >> all_nums[i].value;
        value_to_node_idx[all_nums[i].value] = all_nums[i].original_index;

        int popcount;
#if __cplusplus >= 202002L
        popcount = std::popcount(static_cast<unsigned int>(all_nums[i].value));
#else
        popcount = countSetBits(all_nums[i].value);
#endif
        
        if (popcount % 2 != 0) {
            L_partition.push_back(all_nums[i]);
        } else {
            R_partition.push_back(all_nums[i]);
        }
    }

    // 构建二分图的边
    // 为了效率，我们不进行 O(N^2) 的比较，而是对每个数生成它的“邻居”
    for (const auto& num_info : L_partition) {
        int u_val = num_info.value;
        int u_idx = num_info.original_index;
        for (int i = 0; i < 31; ++i) {
            int neighbor_val = u_val ^ (1 << i);
            auto it = value_to_node_idx.find(neighbor_val);
            if (it != value_to_node_idx.end()) {
                // 找到了一个在 R 部的邻居
                int v_idx = it->second;
                adj[u_idx].push_back(v_idx);
            }
        }
    }

    // 计算最大匹配
    int max_matching_size = 0;
    for (const auto& num_info : L_partition) {
        // 每次为新的 L 部节点寻找匹配前，重置 visited 数组
        std::fill(visited + 1, visited + n + 1, false);
        if (dfs_match(num_info.original_index)) {
            max_matching_size++;
        }
    }

    // 最大独立集的大小 = 总节点数 - 最大匹配数
    std::cout << n - max_matching_size << '\n';
    
    // 找出最大独立集的成员
    // 1. 先反向标记 R 部的匹配关系，方便后续判断
    std::vector<int> r_match(n + 1, 0);
    for(const auto& num_info : R_partition) {
        if(match[num_info.original_index] != 0) {
            r_match[match[num_info.original_index]] = num_info.original_index;
        }
    }

    // 2. 重新进行一次 DFS 来标记 MIS 中的点
    std::fill(visited + 1, visited + n + 1, false);
    for (const auto& num_info : L_partition) {
        // 从 L 部所有未匹配的点出发
        if (r_match[num_info.original_index] == 0) {
            find_mis_nodes(num_info.original_index);
        }
    }

    // 3. 输出结果
    // L 部中被访问到的 + R 部中未被访问到的
    bool first = true;
    for (const auto& num_info : L_partition) {
        if (visited[num_info.original_index]) {
            if (!first) std::cout << " ";
            std::cout << num_info.value;
            first = false;
        }
    }
    for (const auto& num_info : R_partition) {
        if (!visited[num_info.original_index]) {
            if (!first) std::cout << " ";
            std::cout << num_info.value;
            first = false;
        }
    }
    std::cout << '\n';

    return 0;
}

小提示：代码中 find_mis_nodes 的实现稍微简化了一下，直接用 visited 数组来标记属于最大独立集的 L 部成员和不属于最大独立集的 R 部成员，最后根据这个 visited 状态来输出结果，逻辑是一样的喵~

复杂度分析

• 时间复杂度: $O(N \log A + |L| \cdot E)$

  • 建图：我们遍历所有 n 个数。对于每个数，我们尝试翻转它的每一位（大约 $\log A$ 次，其中 $A$ 是数字的最大值），然后在 map 中查找。map 操作是 $O(\log N)$。所以建图是 $O(N \cdot \log A \cdot \log N)$。如果用 unordered_map，可以优化到 $O(N \log A)$。我的代码里用了 map，但这个 $O(\log N)$ 因子通常很小。
  • 最大匹配：我们从 L 部的每个节点（最多 n 个）出发进行一次 DFS。每次 DFS 最坏情况下会遍历图中的所有边。图的边数 $E$ 是 $O(N \log A)$。所以这部分是 $O(|L| \cdot E) \approx O(N \cdot N \log A)$。这看起来很慢，但在实际中，由于图的稀疏性和增广过程，它的表现通常比最坏情况好得多，足以通过此题，喵~
  • 寻找独立集成员：一次 DFS/BFS 遍历，复杂度为 $O(V+E) = O(N + N \log A)$。
  • 综上，主要瓶颈在最大匹配的计算上。

• 空间复杂度: $O(N \log A)$

  • all_nums、L_partition、R_partition 等数组总共是 $O(N)$。
  • value_to_node_idx 这个 map 占用 $O(N)$。
  • 邻接表 adj 存储了所有的边，边数是 $O(N \log A)$，所以空间是 $O(N \log A)$。
  • match 和 visited 数组是 $O(N)$。
  • 所以总空间由邻接表主导，为 $O(N \log A)$。

知识点总结

这真是一道非常棒的题，它教会了我们：

1. 问题建模与转化：将看似与图无关的约束条件（二进制位数差异）转化为图论中的边，从而把问题变成一个我们熟悉的图论模型。这是算法竞赛中非常重要的能力！
2. 二分图的判定与性质：通过 popcount 的奇偶性，我们能迅速判定图是二分图。这是二分图问题的一个经典特征。
3. Kőnig 定理的应用：它是连接最大独立集、最小顶点覆盖和最大匹配三大概念的桥梁，是解决二分图上最大独立集问题的标准武器。
4. 二分图最大匹配算法：掌握匈牙利算法（或 Dinic 等网络流算法）是解决这类问题的基础。
5. 从匹配构造独立集：学会如何从最大匹配的结果出发，通过一次遍历找出最小顶点覆盖，进而得到最大独立集的具体成员。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！加油，喵~！