K - Necklace
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
题意：
给出N个珠子，要把他们连成串，每个珠子都要用上，有多少种连法。重点是dp状态转移方程。
代码：
1 /* 2 给出的珠子要全部用上，因此只要最后的状态dp[i][j]中的j能够与第一个珠子相连就行，其中i表示取珠子 3 的状态，每多加一颗珠子他的dp数就是加上没加之前的dp数(重点！). 4 */ 5 #include<iostream> 6 #include<string> 7 #include<cstdio> 8 #include<cmath> 9 #include<cstring> 10 #include<algorithm> 11 #include<vector> 12 #include<iomanip> 13 #include<queue> 14 #include<stack> 15 using namespace std; 16 int n,m,a,b; 17 bool d[19][19]; 18 long long dp[1<<19][19]; //用int过不了 19 int main() 20 { 21 while(scanf("%d%d",&n,&m)!=EOF) 22 { 23 memset(dp,0,sizeof(dp)); 24 memset(d,0,sizeof(d)); 25 for(int i=0;i<m;i++) 26 { 27 scanf("%d%d",&a,&b); 28 a--; //这里减一是为了后面写循环简便，也可以不减一 29 b--; 30 d[b][a]=1; 31 d[a][b]=1; 32 } 33 dp[1][0]=1; //初始化第一个当放一个钥匙时总数为1 34 for(int i=0;i<(1<<n);i++) 35 { 36 for(int j=0;j<n;j++) 37 { 38 if(dp[i][j]==0) continue; //也可以用!(i&(1<<j))来判断，但后者会更费时 39 for(int k=1;k<n;k++) //k也可以从0开始 40 { 41 if(!d[k][j]) continue; //判断k与j是否能连接 42 if(i&(1<<k)) continue; //判断第K个钥匙是否已算过 43 dp[i|(1<<k)][k]+=dp[i][j]; 44 } 45 } 46 } 47 long long ans=0; 48 for(int i=0;i<n;i++) 49 { 50 if(d[0][i]) ans+=dp[(1<<n)-1][i]; 51 } 52 cout<<ans<<endl; 53 } 54 return 0; 55 }