A Simple Task

题目链接 cf #11D

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll dp[1<<20][20];
int v[20][20];
int main()
{
    ll ans=0;
    int m,n;
    cin>>n>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        x--,y--;
        v[x][y]=v[y][x]=1;
    }
    for(int i=0;i<n;i++)
        dp[1<<i][i]=1;
    for(int s=1;s<(1<<n);s++)
    {
        int st;
        for(int i=0;i<n;i++)
            if((1<<i)&s) {st=i;break;}//找到s当中的第一个点
        for(int e=st;e<n;e++)//枚举s状态中每一个可能在末尾的点
        {
            if(!((1<<e)&s)) continue;//找到s中的点e
            for(int j=st;j<n;j++)//新收进来的点必须要在st的后面，以保证st是状态中的第一个点
            {
                if((1<<j)&s) continue;//j不能是s中的点
                if(v[j][e])
                {
                    dp[s|(1<<j)][j]+=dp[s][e];//你要想到，j是不会等于st的，不满足不属于s的条件，也就是说所有状态s，第一位是st，那么一定
                    if(v[st][j]&& __builtin_popcount(s|(1<<j))>=3) ans+=dp[s][e];//确实有可能e=st，但是上一句的遍历过程保证了dp[i][j]这个数组，当状态i的首位是st且i中包含两个以上点时，j一定不会是st，所以这里ans跟没加一样
                }
            }
        }
    }
    cout<<ans/2<<endl;
    return 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.

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 m lines contains two integers a and b, (1 ≤ a, b ≤ n, a ≠ b) indicating that vertices a and b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.

Output the number of cycles in the given graph.

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

7

The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.

最后

以上就是美满白昼为你收集整理的A Simple Task的全部内容，希望文章能够帮你解决A Simple Task所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。