independent set 1 - 题解

标签与难度

标签: 动态规划, 状压DP, 位运算, 图论, 最大独立集, 子集DP 难度: 2100

题目大意喵~

各位算法大师，你们好呀，喵~ ฅ(๑'▽'๑)ฅ

这道题是关于图论的一个经典问题哦！题目给了我们一个有 $N$ 个顶点和 $M$ 条边的无向图。

首先，我们要知道什么是独立集 (Independent Set)。在一个图里，选出一部分顶点，如果这些顶点之间两两都没有边直接相连，那么它们就组成了一个独立集。就像一群互相不认识的猫猫，可以和平地待在一起！而最大独立集 (Maximum Independent集)，就是顶点数量最多的那个独立集啦。

其次，是导出子图 (Induced Subgraph)。从原来的大图中选出一部分顶点（比如顶点集合 $V'$ ），那么由 $V'$ 和所有连接 $V'$ 中顶点的原始边构成的新图，就是原图关于 $V'$ 的一个导出子图。

我们的任务是：对于原图的所有 $2^N$ 个可能的顶点子集，我们都生成它们对应的导出子图。然后，对每一个导出子图，我们都求出它的最大独立集的大小（也就是顶点数量）。最后，把这 $2^N$ 个最大独立集的大小全部加起来，得到最终的答案！

简单来说，就是： 求所有 $2^N$ 个导出子graph的最大独立集大小之和。

解题思路分析

看到 $2^N$ 这个数字，而且 $N$ 的范围不大（根据内存限制和题目类型，通常在 20-26 之间），我们的猫猫直觉就告诉我们，这很可能是一道需要用状压DP (DP on Subsets / Bitmask DP) 来解决的问题，喵！

直接暴力求解是行不通的。因为对于每个子图，求最大独立集本身是一个 NP-Hard 问题。但幸运的是，我们可以通过一个巧妙的DP来同时计算所有子图的结果！

1. 状态表示

我们可以用一个 $N$ 位的二进制数（我们称之为位掩码或状态，mask）来表示一个顶点的子集。如果 mask 的第 i 位是 1，就代表顶点 i 在这个子集中；如果是 0，就不在。这样，从 0 到 2^N - 1 的所有整数就唯一对应了所有 $2^N$ 个顶点子集。

接下来，我们定义我们的DP数组： dp[mask] 表示由 mask 所代表的顶点集构成的导出子图的最大独立集的大小。

我们的最终目标就是计算 $\sum_{mask=0}^{2^N-1} dp[mask]$ 。

2. 状态转移

现在是最关键的一步：如何从已知的DP值推导出新的DP值呢？

我们从小到大依次计算每个 mask 对应的 dp[mask] 值。对于一个非空的顶点集 mask，我们总可以从中随便挑一个顶点出来，比如说，就挑编号最小的那个吧！在位运算里，这个操作非常方便，我们可以用 __builtin_ctz(mask) (Count Trailing Zeros) 来找到 mask 中最低位的 1 对应的顶点编号，我们叫它 p。

现在，对于这个顶点 p，在 mask 对应的子图的最大独立集中，只有两种可能：

情况一：最大独立集里不包含顶点 p。 如果我们决定不把 p 放入独立集，那么问题就变成了在剩下的顶点集 mask \ {p} 所构成的子图中寻找最大独立集。这个问题的答案我们已经算过了（因为 mask \ {p} 比 mask 小），就是 dp[mask \ {p}]！用位运算来表示，mask \ {p} 就是 mask ^ (1 << p)。

情况二：最大独立集里包含顶点 p。 如果我们决定把 p 放入独立集，那我们的独立集大小就首先获得了 +1。但是，根据独立集的定义，任何与 p 相邻的顶点都不能再被选入了。所以，我们需要在 mask 中，去掉 p 自己，再去掉所有 p 的邻居，然后在剩下的顶点中寻找最大独立集。假设 neighbors[p] 是一个位掩码，表示所有与 p 相邻的顶点以及 p 自己。那么，我们需要在 mask 中排除掉这些顶点，也就是在 mask & (~neighbors[p]) 这个更小的顶点集中寻找最大独立集。这个问题的答案是 dp[mask & (~neighbors[p])]。所以，这种情况下的最大独立集大小就是 1 + dp[mask & (~neighbors[p])]。

综合一下！ 我们想要的是最大独立集，所以我们在这两种情况中取一个较大的结果，喵~ 于是，状态转移方程就出来啦：

dp[mask] = \max(dp[mask \setminus \{p\}], \quad 1 + dp[mask \setminus (N(p) \cup \{p\})])

用位运算写出来就是：

dp[mask] = \max(dp[mask \oplus (1 \ll p)], \quad 1 + dp[mask \ \& \ (\sim \text{adj}[p])])

其中 p = __builtin_ctz(mask)，adj[p] 是一个预处理好的位掩码，代表了顶点 p 和它所有邻居的集合。

3. 实现细节

预处理邻接关系：我们可以用一个数组 adj[N]，其中 adj[i] 是一个整数（位掩码），它的第 j 位为 1 当且仅当 (i, j) 之间有边。为了方便计算，我们可以让 adj[i] 的第 i 位也为 1，这样 adj[i] 就代表了 p 和它所有邻居的集合 N(p) \cup \{p\}。
DP数组大小： $N$ 最大可达 26， $2^{26}$ 大约是 $6.7 \times 10^7$ 。如果用 int (4字节) 存储 dp 数组，会需要 6.7 * 10^7 * 4 字节 ≈ 268MB 内存，这会超出的说！但是，最大独立集的大小不会超过 $N$ （最多26），所以用 char (1字节) 来存储 dp 值就足够了，内存占用瞬间降到 67MB，完全没问题！
循环顺序：我们从 mask = 1 循环到 2^N - 1，依次计算每个 dp[mask]。dp[0] 自然是 0（空集的独立集大小为0）。
求和：计算完所有 dp 值后，再遍历一遍 dp 数组，把所有值加起来。记得用 long long 来存总和，不然可能会溢出哦！

这样，我们就能高效地解决这个问题啦！是不是很奇妙呢，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助你理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 使用 GCC 内置函数来快速找到二进制数中最低位的1的位置
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_ctz(x) _tzcnt_u32(x)
#endif

// 为了让代码更清晰，定义一些别名
using ll = long long;

// dp[mask] 存储由 mask 代表的顶点集构成的导出子图的最大独立集大小
// N 最大为 26，所以 2^26 大约是 6.7e7，用 char 可以节省大量内存
char dp[1 << 26];

// adj[i] 是一个位掩码，表示顶点 i 和它的所有邻居
int adj[26];

int main() {
    // 加速 C++ IO，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // 预处理邻接关系
    // adj[i] 的第 j 位为 1，表示 i 和 j 相邻
    // 为了方便计算，我们把顶点自己也看作自己的“邻居”
    for (int i = 0; i < n; ++i) {
        adj[i] = (1 << i); // 先把自己加入集合
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        // 题目中的顶点编号是从 0 开始还是 1 开始需要注意，这里假设从0开始
        // 如果是从1开始，需要 u--, v--
        // 观察参考代码，顶点编号是从0到n-1
        adj[u] |= (1 << v);
        adj[v] |= (1 << u);
    }

    // dp[0] = 0，空集的最大独立集大小是0，char数组默认初始化为0

    ll total_sum = 0;

    // 遍历所有非空顶点子集
    for (int mask = 1; mask < (1 << n); ++mask) {
        // 找到 mask 中编号最小的顶点 p
        // __builtin_ctz(mask) 返回 mask 的二进制表示中末尾0的数量，
        // 也就是最低位的1所在的索引
        int p = __builtin_ctz(mask);

        // 情况1：不选择顶点 p
        // 此时最大独立集大小等于在 mask \ {p} 子图中的最大独立集大小
        int size_without_p = dp[mask ^ (1 << p)];

        // 情况2：选择顶点 p
        // 此时大小为 1 + 在 (mask 中排除 p 和 p 的所有邻居后) 的子图中的最大独立集大小
        // mask & (~adj[p]) 就能得到排除了 p 和 p 的邻居后的新顶点集
        int size_with_p = 1 + dp[mask & (~adj[p])];

        // 取两种情况的最大值
        dp[mask] = std::max(size_without_p, size_with_p);
        
        // 将当前子图的最大独立集大小累加到总和中
        total_sum += dp[mask];
    }

    std::cout << total_sum << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(2^N)$
- 预处理邻接关系需要 $O(N+M)$ 的时间。
- 核心部分是状压DP的循环，它会遍历从 1 到 2^N - 1 的所有状态。循环体内部的操作（位运算、取最大值等）都是常数时间 $O(1)$ 的。
- 最后求和也需要遍历一次DP数组，时间是 $O(2^N)$ 。
- 所以，总的时间复杂度由DP部分主导，为 $O(M + 2^N)$ ，因为 $2^N$ 远大于 $M$ ，可以简化为 $O(2^N)$ 。
空间复杂度: $O(2^N)$
- 我们使用了 dp 数组来存储每个子集的结果，其大小为 $2^N$ 。
- adj 数组的大小为 $N$ 。
- 因此，主要的空间开销是 dp 数组，空间复杂度为 $O(N + 2^N)$ ，简化为 $O(2^N)$ 。

知识点总结

这道题真是一道非常经典的状压DP教学题呢！通过它，我们可以学到：

状压DP (DP on Subsets)：当问题涉及到对一个大小为 $N$ (通常 $N \le 26$ ) 的集合的所有子集进行计算时，可以考虑使用位掩码来表示子集，并进行动态规划。
最大独立集问题: 虽然在一般图上是NP-Hard问题，但在特定情况下（如本题要求遍历所有子图）或在特殊图（如树）上，可以用DP等方法高效求解。
状态转移的思考方式: 解决DP问题的核心是找到正确的状态转移方程。对于子集DP，一个常见的技巧是“选/不选”某个元素。通过分析选择一个特定元素（如lowbit）带来的影响，将原问题分解为更小的子问题。
位运算技巧:
- 1 << i: 生成第 i 位为1的掩码。
- mask & (1 << i): 检查 mask 中第 i 位是否为1。
- mask | (1 << i): 将第 i 位设为1。
- mask ^ (1 << i): 翻转第 i 位（在已知第i位为1时，等价于 mask - (1 << i)，即移除元素）。
- ~mask: 按位取反。
- __builtin_ctz(mask): 快速找到最低位的1，是处理子集DP时非常有用的工具。
空间优化意识: 在处理指数级大小的数组时，要对数据类型的大小非常敏感。用 char 代替 int 或 long long 是一个常见的、救命的技巧！

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

independent set 1 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 状态表示 ​

2. 状态转移 ​

3. 实现细节 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​