hdu 3091 Necklace 状态压缩dp *******

Necklace

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 522    Accepted Submission(s): 168

Problem Description

One day , Partychen gets several beads , he wants to make these beads a necklace . But not every beads can link to each other, every bead should link to some particular bead(s). Now , Partychen wants to know how many kinds of necklace he can make.

 

Input

It consists of multi-case .
Every case start with two integers N,M ( 1<=N<=18,M<=N*N )
The followed M lines contains two integers a,b ( 1<=a,b<=N ) which means the ath bead and the bth bead are able to be linked.

 

Output

An integer , which means the number of kinds that the necklace could be.

 

Sample Input

3 3

1 2

1 3

2 3

Sample Output

2

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;

int n,m;
vector <int> a[20];
long long dp[(1<<18)+2][20];
void make_ini()
{
    int i,j;
    int s,r,u;
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;
    for(i=1;i<(1<<n);i++)
    {
        for(j=0;j<n;j++)
        {
            if(dp[i][j]==0)continue;
            for(s=0;s<a[j].size();s++)
            {
                u=a[j][s];
                if( (i&(1<<u))>0 ) continue;
                r=( i | (1<<u) );
                dp[r][u]+=dp[i][j];
            }
        }
    }
    long long Sum=0;
    for(i=0;i<a[0].size();i++)
        Sum+=dp[(1<<n)-1][a[0][i]];
        printf("%I64d
",Sum);
}
int main()
{
    int i,x,y;
    while(scanf("%d%d",&n,&m)>0)
    {
        for(i=0;i<n;i++)
        {
            a[i].clear();
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            x--;
            y--;
            a[x].push_back(y);
            a[y].push_back(x);
        }
        make_ini();
    }
    return 0;
}