简单环计数(状压 DP)
统计无向图里长度 ≥3 的简单环个数。dp[S][i] + 固定最小值起点 + lowbit 判环,O(2^n·(n+m)),附子集遍历等小知识点
问题(CF 11D):给一张无向简单图,统计简单环(长度 ≥ 3,环上点在环内互不相同,允许有弦)的个数。
n ≤ 19 → 状压 DP。
代码(CF 11D 已 AC)
#include <bits/stdc++.h>
using namespace std;
#define int long long
static const long long MOD = 998244353;
const int N = 19;
vector<int> g[N];
int n,m;
int dp[1<<N][N+1];
void sol() {
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++) dp[1<<(i-1)][i]=1;
int ans=0;
for(int s=0;s<(1<<n);s++){
for(int i=1;i<=n;i++){
if(!dp[s][i]) continue;
for(auto v:g[i]){
if((s&-s)>(1<<(v-1))) continue;
if(s&(1<<(v-1))){
if((s&-s)==(1<<(v-1))) ans+=dp[s][i];
}else{
dp[s|(1<<(v-1))][v]+=dp[s][i];
}
}
}
}
cout<<(ans-m)/2<<endl;
}
signed main(){
int T=1;
//cin>>T;
while(T--){
sol();
}
return 0;
}
状态设计
dp[S][i] = 以 S 中编号最小的点为起点、当前停在 i、已经访问过 S 中所有点的路径条数。
- 起点固定为
S的最低位 →lowbit(S) = S & -S,它对应1 << (起点-1); - 初始化:每个单点集
dp[1<<(i-1)][i] = 1(只有自己); - 转移(枚举
i的邻点v):
| 情况 | 处理 | 原因 |
|---|---|---|
v ∉ S | dp[S∪{v}][v] += dp[S][i] | 继续往外走 |
v ∈ S 且 v 就是起点 | ans += dp[S][i] | 回到起点 → 形成一个环 |
v ∈ S 但不是起点 | 跳过 | 否则同一个环会被重复统计多次 |
关键约束:if((s&-s) > (1<<(v-1))) continue;
只允许走向编号不小于起点的点。这样每个环只会在它的最小编号点处被统计一次,不会因为起点不同而重复。
最后一步 (ans - m) / 2:
- 长度 2 的”往返”
start → v → start被当成环数了,恰好每条边一次 → 减m; - 每个长度 ≥3 的环会被两个方向各数一次 → 除以 2。
小知识点
1. 子集遍历的四种写法
// ① 遍历所有子集
for(int s = 0; s < (1 << n); s++) { }
// ② 遍历 s 的所有「非空子集」(含 s 本身)
for(int t = s; t; t = (t - 1) & s) { }
// ③ 遍历 s 的所有「真子集」(不含 s 本身,也不含空集)
for(int t = (s - 1) & s; t; t = (t - 1) & s) { }
// ④ 遍历 s 的所有「超集」
for(int t = s; t < (1 << n); t = (t + 1) | s) { }
- 写法 ②③ 的核心是
(t - 1) & s:从t里去掉最低的 1 之后,再和s取交,得到下一个更小的子集; - 把「枚举所有
s」和「枚举s的子集」套起来,总复杂度是 O(3^n)(每个点有三种状态:不在 s / 在 s 不在 t / 在 t)——斯坦纳树、集合划分 DP 都靠这个。
2. lowbit 家族
int lowbit = s & -s; // 最低位的 1(本题就是"起点"对应的位)
int rest = s & (s - 1); // 去掉最低位的 1
int pos = __builtin_ctz(s); // 最低位的下标(0 开始,等价于 log2(lowbit))
int cnt = __builtin_popcount(s); // 集合大小
本题用 s & -s 既当「起点是谁」,又当「v 是不是起点」的比较对象:
if((s&-s) > (1<<(v-1))) continue; // v 编号比起点小 → 不走
if((s&-s) == (1<<(v-1))) ans += dp[s][i]; // v 就是起点 → 成环
3. 为什么 for (s = 0; s < (1<<n); s++) 递增就够
转移只从 s 走到 s | (1<<(v-1)),而任何 s | bit > s(加了位只会变大),所以按 s 从小到大枚举时,用到的状态一定已经算完——天然拓扑序,不需要按 popcount 分层。
4. 判断 / 修改某一位
bool in = s >> (v - 1) & 1; // 或写成 s & (1 << (v - 1))
int add = s | (1 << (v - 1)); // 加进来
int del = s & ~(1 << (v - 1)); // 删掉
5. 坐标习惯要统一
代码里点编号是 1 到 n,位是 0 到 n-1,所以永远是 1 << (v - 1)。
写混(比如某处写 1 << v)会静默出错、且很难查——这是本题最常见的翻车点。
复杂度
| 复杂度 | 说明 | |
|---|---|---|
| 时间 | O(2^n · (n + m)) | 每个状态枚举 i 和 i 的邻边 |
| 空间 | O(2^n · n) | dp[1<<19][20],long long 约 84MB(CF 11D 内存 256MB 够用) |
空间优化:若内存吃紧,把 dp 换成 32 位 int(约 42MB);答案不超过 19!/2 ≈ 6e16,long long 存答案够用。
易错点 / 易混点
| 问题 | 错误后果 | 正确做法 |
|---|---|---|
| 起点不固定 | 同一个环被数很多次,答案爆炸 | 用 s & -s 固定为最小点 |
v ∈ S 但非起点时也累加 | 重复计数 | 只在 v == 起点 时累加 |
忘了 (ans - m) / 2 | 多算长度 2 的往返、且每个环算两次 | 先减 m 再除 2 |
1 << (v-1) 写成 1 << v | 位与点错位,答案随机 | 点 1..n 对应位 0..n-1 |
| 有重边时不去重 | 同一条边被当多条路径,环数虚高 | 本题保证简单图;否则先对邻接表去重 |
dp 用 long long 又内存紧张 | MLE | 状态数组用 int,答案单独用 long long |
n < 3 | 无输出/负数 | 特判或让公式自然给 0(ans=0 时 (0-m)/2 需注意 m 也要为 0) |
同类题
- CF 11D A Simple Task — 本题
- 统计三角形个数:
n ≤ 2e5的图上用「按度数分类 / bitset」做,不是这个状压套路 - 统计环的个数(含重边、模数):状态按
popcount分层 + 组合数,n很大时通常是计数组合题
延伸
- 状压 DP 的三件套:位运算判集合、
lowbit找代表元、子集枚举做合并; - 图上状压(本题)与集合状压(如
dp[mask]表示选了哪些点/物品)是两种不同套路,别混用; - 若题目要求输出每个环而不是个数,状压就不够了,要用「删点后的生成环 / DFS 枚举规范环」。