A Simple Task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}