Codeforce 11D A Simple Task

September 5, 2019

1324views

275 words

## 状压DP

题目：[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

如果觉得我的文章对你有用，请随意赞赏

Codeforce 11D A Simple Task