CodeForces 11D A Simple Task

今天做的不太一样的状压，从去年的专题找的，看到学长并没有写是已经写过了么？
可能是因为跟图论相关的原因吧。

题意：
给你一个简单图，让你找出简单环的数量。
附 ： 简单环就是没有重边和重点的环。
点数为 19 。

思路：
19个点，一般很容易想到状压和二维……根据数据猜算法？
事实上我是没有想到二维的

dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ，初始对每个状态 dp [ 1<< i ][ i ] 设置为 1
对于每一个状态，固定的从最小的一位 1 作为起点，从这个起点开始扩散，如果能回到这个起点，就进行计数。

因为对于一个环，枚举起点和终点的话，会存在起点到终点，和以终点为起点的情况。
比如说 1-> 2 -> 3 ->1 和 3 -> 2 -> 1 -> 3

AC Code

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 20;
typedef long long ll;

int map[maxn][maxn], n, m, u, v;
ll dp[1 << maxn][maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        u--, v--;
        map[u][v] = map[v][u] = 1;
    }
    ll ans = 0;
    for (int i = 0; i < maxn; i++)
        dp[1 << i][i] = 1;
    for (int st = 1; st < (1 << n); st++) {
        int s = __builtin_ctz(st); //右边第一个1的位置
        for (int e = s; e < n; e++) {  //枚举集合元素 作为当前位置
            if (st & (1 << e)) {
                for (int i = s; i < n; i++) {  // 扩散状态
                    int nst = st | (1 << i);
                    if (map[e][i] && (st & (1 << i)) == 0) { //新状态
                        dp[nst][i] += dp[st][e];
                        if (map[i][s] && __builtin_popcount(nst) > 2) // 能回到起点 1的数量也就是边数大于2
                            ans += dp[st][e]; 
                    }
                }
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}