codeforce 11D A Simple Task

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 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
Output the number of cycles in the given graph.

Examples
input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
output
7
Note
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.

题意

求一个图长度大于等于三的哈密顿路径数目。

题解

状压，f[i][j]表示状态为i时，以j结尾的路径条数。

如果下一个点能回到已经走过的一个点中，那么就是一个回路了。

为了避免重复计算，回到的点为走过的最小的点。（这是一个优化，少了枚举最小点这个循环）

长度为2的哈密顿路径会计算到，可以不做处理，最后减去边的条数即可，每个环会算两遍，最后要除以2.

#include <cstdio>
using namespace std;
long long f[1<<19][19],map[20][20],n,m,x,y;
int start(int now)
{
    for (int i=0;i<n;i++)
        if ((1<<i)&now)
            return i;
}
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),x--,y--,
        map[x][y]=1,map[y][x]=1;
    long long ans=0,cnt=(1<<n)-1;
    for (int i=0;i<n;i++)
        f[1<<i][i]=1;
    for (int i=1;i<=cnt;i++)
        for (int j=0;j<n;j++)
            if (f[i][j])
            {
                int st=start(i);
                for (int k=st;k<n;k++)
                    if (j!=k && map[j][k])
                        if (i&(1<<k))
                            if (k==st)
                                ans+=f[i][j];
                            else;
                        else
                            f[i|(1<<k)][k]+=f[i][j];
            }
    ans-=m;
    ans/=2;
    printf("%lld\n",ans);
}