状压dp找寻环的个数 Codeforces Beta Round #11 D

//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = ;
LL dp[ << maxn][maxn + ];
int a[maxn + ][maxn + ];
int n, m;void get_min(int val, int &cnt, int &st){
int pos = ;
while (val){
if (val & ) st = min(st, pos), cnt++;
val >>= ;
pos++;
}
}
///定义dp[i][j]表示i是圈的集合，j表示该集合的终点，定义起点为这些走过的点里面最小的
int main(){
cin >> n >> m;
for (int i = ; i <= m; i++){
int u, v; scanf("%d%d", &u, &v);
u--, v--;
a[u][v] = a[v][u] = ;
}
LL ans = ;
for (int i = ; i < n; i++) dp[ << i][i] = ;///初始化
for (int i = ; i < ( << n); i++){
int cnt = , st = n;
get_min(i, cnt, st);
for (int j = ; j < n; j++){
if (dp[i][j]){///目前集合为i，终点为j。而且根据放入集合的顺序，j必然是在i集合里面的
if (a[st][j] && cnt >= ){///放入集合的最终的终点一定得是在st的旁边。否则会将形不成环的放入ans中
ans += dp[i][j];
}
for (int k = st + ; k < n; k++){///放入终点大于st的。根据定义st必然为最小的起点。
///然后k<st的已经在更小的状态中全部都计算过了
if (a[j][k] && !(i & (1 << k))){
dp[i | (1 << k)][k] += dp[i][j];
}
}
}
}
}
/*haha;
for(int i = 0; i < n; i++){
for (int j = 0; j < (1 << n); j++){
printf("%lld ", dp[j][i]);
}
cout << endl;
}*/
cout << ans / << endl;
return ;
}