CodeForces 11D(动态规划-状压dp)-蒲公英云

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

以你之姓@ 2022-06-01 03:41 299阅读 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

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;
}