Loading... ## 状压DP <!--more--> 题目:[D. A Simple Task](https://codeforces.com/contest/11/problem/D) 给一个图,找出图中所有环的个数。 n最大只有19,考虑状压DP。 如何找环呢?无非就是从一个起点出发经过若干个点后又回到了该点。假设从$u$经过若干个点到$v$一共有$k$种走法,此时$v-u$有一条边,那么这时环就出来了,并且个数是$k$个 $dp[s][j]$表示经过状态$s$到达$j$的方案数,考虑$j-v$的的一条边。 - 如果$v$不在$s$里面,经过状态$(s|(1<<v))$到达$v$节点的方案数加上$dp[s][j]$,即$dp[s|(1<<v)][v]+=dp[s][j]$ - 如果$v$在$s$里面,那么此时构成了环,但是这样会造成重复计算,一个环里必定有编号最小的节点,所以我们规定环的起点为编号最小的节点,同时两条边构成的环不计入答案。 ```cpp #include <stdio.h> #include <string.h> #include <algorithm> #include<iostream> using namespace std; const int N = 20; typedef long long ll; struct E{ int to, next; }edge[1005]; int head[N], tot; int n, m; void addedge(int from, int to) { edge[++tot].to = to; edge[tot].next = head[from]; head[from] = tot; } ll dp[1<<N][N]; int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); addedge(u - 1, v - 1); addedge(v - 1, u - 1); } for (int i = 0; i <= n; i++) dp[1 << i][i] = 1; ll ans = 0; for (int i = 1; i < (1<<n); i++) { for (int j = 0; j < n; j++) { if (!dp[i][j]) continue; for (int k = head[j]; k != -1; k = edge[k].next){ int v = edge[k].to;//从j->v,由于不能重复计算,所以起点固定为小的开始 if ((i&(-i))>(1 << v)) continue;//起点不是最小,不算 if ((i >> v) & 1){ if(((1<<j)|(1<<v))==i) continue; //两条边构成的环不算 if ((i&(-i)) == (1 << v)) ans += dp[i][j]; } else{ dp[i | (1 << v)][v] += dp[i][j]; } } } } printf("%lld\n", ans / 2); return 0; } ``` Last modification:September 5th, 2019 at 08:22 am © 允许规范转载 Support 如果觉得我的文章对你有用,请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
One comment
嗯嗯!你写的很有道理!(。•ˇ‸ˇ•。)