CodeForces 11D(动态规划-状压dp)

以你之姓@ 2022-06-01 03:41 225阅读 0赞

问题描述:

Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 19, 0 ≤ m) – respectively the number of vertices and edges of the graph. Each of the subsequent mlines contains two integers a and b, (1 ≤ a, b ≤ n, a ≠ b) indicating that vertices aand b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.

Output

Output the number of cycles in the given graph.

Example

Input

4 6
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4

Output

题目题意:求一个无向图环的个数

题目分析:dp\[i\]\[j\]表示在i状态下，最后一个为节点j，能到达此状态的方式数，(我看了一些博客，有的人说保存的是环的个数，感觉不是特别妥，最简单的例子，初始化为1的时候，dp\[1<<(i-1)\]\[i\]=1,不一定存在自环），如果存在一条路G\[j\]\[pos\],pos为第一个节点，那么ans+=dp\[i\]\[j\];

代码如下:

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    const int maxn=20;
    bool G[maxn][maxn];
    ll dp[(1<<20)][maxn];
    bool check (int n)//节点个数大于等于3才行
    {
        int cnt=0;
        for (int i=1;i<=20;i++) {
            if (n&(1<<(i-1))) cnt++;
        }
        return cnt>=3;
    }
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset (G,false,sizeof (G));
        memset (dp,0,sizeof (dp));
        for (int i=1;i<=m;i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a][b]=G[b][a]=true;
        }
        ll ans=0;
        for (int i=1;i<=n;i++) {
            dp[1<<(i-1)][i]=1;
        }
        for (int i=1;i<(1<<n);i++) {
            int pos=0;
            for (int l=1;l<=20;l++) {//找头
                if (i&(1<<(l-1))) {
                    pos=l;
                    break;
                }
            }
            for (int j=pos;j<=n;j++) {
                if (i&(1<<(j-1))) {
                    for (int k=pos;k<=n;k++) {
                        if (!(i&(1<<(k-1)))&&G[j][k]) {
                            dp[i|(1<<(k-1))][k]+=dp[i][j];
                            if (G[pos][k]&&check(i|(1<<(k-1)))) ans+=dp[i][j];
                        }
                    }
                }
            }
    
        }
        printf("%lld\n",ans/2);//重复了一半+
        return 0;
    }