给定 \(n\) 个点 \(m\) 条边的简单图,计算图中有多少个简单环
\(1 ≤ n ≤ 19, 0 ≤ m\)
状压dp
状态表示:\(f[i][j]\) 表示状态为 \(i\) 时,起点为 \(i\) 的最低位,终点为 \(j\) 时的最少环数
状态计算:\(f[i|1<<k][k]+=f[i][j]\),其中 \(j\) 和 \(k\) 之间存在一条边
分析:当 \(k\) 和起点相等时说明形成了环,统计到答案即可,否则转移到新的状态中去,注意 \(k\) 不能超过最低位的起点,否则会与定义矛盾,之所以这样定义是为了去重,但最后一个环可能是有两个点组成的,且环顺时针和逆时针重复算了
时间复杂度:\(O(n^2\times 2^n)\)
// Problem: D. A Simple Task // Contest: Codeforces - Codeforces Beta Round #11 // URL: https://codeforces.com/contest/11/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=20; int n,m; bool a[N][N]; LL f[1<<N][N],res; int main() { cin>>n>>m; int all=1<<n; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; x--,y--; a[x][y]=a[y][x]=true; } for(int i=0;i<n;i++)f[1<<i][i]=1; for(int i=1;i<=all;i++) for(int j=0;j<n;j++) { if(!f[i][j])continue; for(int k=0;k<n;k++) { if(!a[j][k])continue; if((i&-i)>1<<k)continue; if(i&(1<<k)`) { if(1<<k==(i&-i))res+=f[i][j]; } else f[i|1<<k][k]+=f[i][j]; } } cout<<(res-m)/2; return 0; }