代码源 每日一题 div1 环的数量

环的数量

原题链接

题目大意

给定一张含有 ? 个点，? 条边的简单图，求简单环的数量。

思路

看到$n<=19$这个数据范围，我们来考虑状态压缩DP，想到一个类似的哈密顿回路问题，那么这个题也可以用类似的方法来解决

状态设计：$f[i][j]$为当前经过的点集为i，且当前在j号点上的路径数量。其中起点为low(i), 后面解释这个起点的含义。

那环怎么解决？可以这样规定，假设有一个环，那它的状态为i，low为$i$的最低有效位(也就是最低为1的那个位），比如$10010_2$, $low=1$。那么这个环可以表示为low->x->y->z->…->low

这样子表示有一个好处，那就是对于每一个有效的环，我们只关心这个环之中最低的那个位是谁，这样就不用考虑重复计算的问题。

for(int mask = 1; mask < 1 << n; mask++) {
    if(__builtin_popcount(mask) <= 2) continue;int low = __builtin_ctz(mask);//从比low更高的位开始计算for(int j = low + 1; j < n; j++) {
    if(mask >> j & 1) {
    //.....}}
}

状态设计已经考虑完毕，我们来考虑一下怎么进行状态转移？
考虑$j$可以到达的所有点u，如果u==low，那么说明我们找到了一个环。

反之我们计算$f[mask][j]$，考虑到表示的是走到当前的j点，所以我们记上一个点为u, 所有到达u时，路径数量为$f[mas{k}^{(}1<<j)][u]$

即状态转移为
$f[mask][j]+=f[mask?(1<<j)][u];$

此外，要注意一些小问题，由于这里的状态设计是路径，所以我们初始化时，对于每一条边a->b, 有$f[(1<<a)|(1<<b)][max(a,b)]=1$，因为起点固定为最小的那个点，所有我们当前点是更大的那个点。

另外，观察上面的出现环的条件，不难发现，对于每个环，都有两个点比low更大，所以环的数量我们会重复计算一次，因此需要把答案/2。

代码

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
using tp = tuple<int,int,int>;
typedef pair<int,int> PII;
const int N = 20, M = 3010, mod = 998244353, INF = 1e9;
bool multi = false;int n, m;
vector<int> g[N];
LL f[1 << N][N];
void solve() {
    cin >> n >> m;while(m--) {
    int a, b;cin >> a >> b;a--, b--;g[a].push_back(b), g[b].push_back(a);f[(1 << a) + (1 << b)][max(a, b)] = 1;}LL res = 0;for(int mask = 1; mask < 1 << n; mask++) {
    if(__builtin_popcount(mask) <= 2) continue;int low = __builtin_ctz(mask);for(int j = low + 1; j < n; j++) {
    if(mask >> j & 1) {
    bool cycle = false;for(int u: g[j]) {
    if(u == low) cycle = true;if(mask >> u & 1) f[mask][j] += f[mask ^ (1 << j)][u];}if(cycle) res += f[mask][j];}}}cout << res / 2 << endl;
}int main() {
    
#ifdef ONLINE_JUDGE
#else freopen("D.txt", "r", stdin);
#endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T = 1;if(multi) cin >> T;while (T--) solve();return 0;
}