状压 DP 进阶：求无向图环的数量 (CF11D 简单的任务)
在图论和动态规划中，统计图中简单环的数量是一个经典问题。当图的节点数 n \leq 19 时，极其契合 O(2^n \cdot n^2) 的时间复杂度，这正是典型的状态压缩 DP (状压 DP) 的应用场景。
本文将详细解析例题 CF11D A Simple Task 的核心解法——按秩转移与去重技巧。
1. 题目大意
给定一个 n 个点 m 条边的无向图（无重边和自环），点数 n \leq 19 ，求无向图中简单环的数量。（简单环的定义：至少包含 3 个点，且除了起点和终点相同外，其余顶点均不相同的路径）。
2. 状态定义与“按秩转移”技巧
为什么不能直接定义终点和起点？
一个直观的思路是：求环，也就是求起点和终点相连的路径。设 f[S][i][j] 表示当前经过的点集为 S ，起点为 i ，当前终点为 j 的路径条数。但由于 |S| = 2^n 、 i,j \in [0,n) ，状态总数为 O(2^n \cdot n^2) 。对于空间和时间来说，都有超限的风险。
降维打击：按秩转移 (固定起点法)
为了压缩掉“起点”这一个维度，并且防止同一个环被多个不同的起点重复统计（例如环 A-B-C-A，不应该被视为 B 起点、C 起点各一次），我们需要一种强制的 “顺序”：
核心思路：强制规定每一个环的起点，必须是该环所有节点中编号最小的那一个。
在二进制表示集合 S 时，集合中编号最小的点，恰好就是 lowbit(S) 对应的点！ 因此，我们可以重新定义状态： f[S][i] 表示：当前经过的点集为 S ，当前停留在点 i ，且该路径的起点强制为 lowbit(S) 的路径条数。
这样，状态数锐减为 O(2^n \cdot n) ，完全可以接受。
3. 状态转移方程推导
我们在枚举点集 S 的时候，从小到大枚举。对于每一个状态 f[S][i] ：
- 枚举当前路径的末端点 i （要求 i \in S 且 f[S][i] > 0 ）。
- 枚举 i 的邻接点 j 作为下一步要走的点。
此时会面临三种情况（重点理解）：
- 情况 A： j 的编号比起点（
lowbit(S)）还要小。 这破坏了我们“以最小编号为起点”的原则，直接continue跳过，不予转移。 代码体现：if (low(S) > (1 << j)) continue; - 情况 B： j 恰好等于起点（
lowbit(S)）。 说明我们绕了一圈又回到了起点，成功找到了一个环！ 我们将当前路径数累加到总答案中：ans += f[S][i]。 - 情况 C： j 在集合 S 之外，且编号大于起点。 说明路径可以继续向外延伸，我们把点 j 加入集合，更新状态：
f[S | (1 << j)][j] += f[S][i]
4. 答案的去重逻辑 (为什么输出 (ans - M) >> 1？)
跑完上述的 DP 之后，我们得到的 ans 并不是最终真正的环的数量，它包含了两种“假环”或“重复环”：
- 长度为 2 的路径被当成了环（单条边往返）： 由于图是无向的，对于任意一条边
u - v（假设 u < v ）。 在 DP 中，起点为 u ，走到了 v ，此时集合为 \{u, v\} 。下一步枚举邻接点时，发现 v 的邻接点有 u ，且 u 恰好是起点，于是ans会加上 1。 图中有 M 条边，所以ans中多算了 M 个实际上只是单条边的“二元环”。 - 每个真正的环被顺时针、逆时针各算了一次： 对于一个真正的环 A-B-C-A（A 编号最小）。 我们的算法会统计到 A → B → C → A，也会在另一条路径扩展时统计到 A → C → B → A。因此每个真正的简单环被算了 2 次。
最终修正公式： 真正的简单环数量 = \frac{\text{ 总计 ans 数} - \text{边数} M}{2} ，即代码中的 (ans - M) >> 1。
5. 完整代码及详尽注释
#include <bits/stdc++.h>
#define MAXN 20
#define MAXS 600010
#define LL long long
// 宏定义 lowbit，用于快速获取集合 s 中编号最小的节点 (即最低位的 1)
#define low(x) ((x) & (-(x)))
using namespace std;
LL ans;
int N, M, Mx;
int A[MAXN][MAXN]; // 邻接矩阵
LL f[MAXS][MAXN]; // DP 数组 f[s][i]
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int i, j, s, u, v;
if (!(cin >> N >> M)) return 0;
// Mx 表示满状态，即 (1 << N) - 1
Mx = (1 << N) - 1;
// 读入边并建图，注意将编号从 1~N 映射为 0~N-1
for (i = 1; i <= M; ++i) {
cin >> u >> v;
u--; v--;
A[u][v] = A[v][u] = 1;
}
// 初始化：单个节点也视为一条路径的起点
// 对于每一个节点 j，它构成的单元素集合表示为 i = 1 << j
for (i = 1, j = 0; j < N; ++j, i <<= 1) {
f[i][j] = 1;
}
// 开始状压 DP，从小到大枚举状态 s
for (s = 1; s <= Mx; ++s) {
// 枚举当前所在节点 i
for (i = 0; i < N; ++i) {
// 如果节点 i 不在集合 s 中，或者状态 s 下以 i 结尾的路径数为 0，则跳过
if (!( (1 << i) & s ) || !f[s][i]) continue;
// 枚举下一步要走的节点 j
for (j = 0; j < N; ++j) {
// 如果 i 和 j 之间没有边，跳过
// 如果 j 的编号比起点 low(s) 还要小，说明破坏了以最小编号为起点的原则，跳过
if (!A[i][j] || low(s) > (1 << j)) continue;
// 情况 1：如果下一步走到的节点 j 恰好等于起点
if ((1 << j) == low(s)) {
ans += f[s][i]; // 闭合成环，累加答案
}
// 情况 2：如果 j 之前没有被访问过 (不在集合 s 中)
else if (!( (1 << j) & s )) {
f[s | (1 << j)][j] += f[s][i]; // 扩展路径并转移状态
}
}
}
}
// 扣除长度为 2 的往返路径 (即原图的 M 条边)，并除以 2 消除正反两个方向的重复统计
cout << ((ans - M) >> 1) << "\n";
return 0;
}
总结
这道题是学习 “按秩转移 (固定极值点去重)” 非常经典的例题。在很多需要处理子集、路径或组合的状压 DP 中，为了避免排列导致的重复计算，我们常常强制选取一个特征值（如最小 / 最大索引）作为整个组合的“锚点”，这能有效将复杂度降低一个维度。