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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 using namespace std;

 int n,m;

 vector <int> a[];

 long long dp[(<<)+][];

 void make_ini()

 {

     int i,j;

     int s,r,u;

     memset(dp,,sizeof(dp));

     dp[][]=;

     for(i=;i<(<<n);i++)

     {

         for(j=;j<n;j++)

         {

             if(dp[i][j]==)continue;

             for(s=;s<a[j].size();s++)

             {

                 u=a[j][s];

                 if( (i&(<<u))> ) continue;

                 r=( i | (<<u) );

                 dp[r][u]+=dp[i][j];

             }

         }

     }

     long long Sum=;

     for(i=;i<a[].size();i++)

         Sum+=dp[(<<n)-][a[][i]];

         printf("%I64d\n",Sum);

 }

 int main()

 {

     int i,x,y;

     while(scanf("%d%d",&n,&m)>)

     {

         for(i=;i<n;i++)

         {

             a[i].clear();

         }

         for(i=;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             x--;

             y--;

             a[x].push_back(y);

             a[y].push_back(x);

         }

         make_ini();

     }

     return ;

 }

巴特西

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

Necklace

最新文章

热门文章