A Simple Task CodeForces - 11D

A Simple Task CodeForces - 11D

題意：輸出一個無向圖的簡單環數量。簡單環指無重覆邊的環。保證圖無重邊自環。

ans[i][j]表示"包含i中的點，以i中第一個點為起點，以j為終點"的路徑條數。

對於某個i，枚舉當前終點j（顯然不能是首個點），產生一個狀態。再枚舉上一次終點k，如果能轉移就轉移。

如果i中點數大於2且j到i中第一個點有路，就認為產生了環。最後每個環記錄了兩遍，要除以2。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL n,m;
 7 bool ok[30][30];
 8 LL ans[1000000][22];
 9 LL anss;
10 int main()
11 {
12     LL a,b,i,j,k,fi,p,pp;
13     scanf("%lld%lld",&n,&m);
14     for(i=1;i<=m;i++)
15     {
16         scanf("%lld%lld",&a,&b);
17         ok[a][b]=ok[b][a]=true;
18     }
19     for(i=1;i<(1<<n);i++)
20     {
21         pp=__builtin_popcountll(i);
22         if(pp==1)
23         {
24             //for(j=1;j<=n;j++)
25                 ans[i][__builtin_ffsll(i)]=1;
26         }
27         else
28         {
29             fi=__builtin_ffsll(i);
30             for(j=1;j<=n;j++)
31                 if((i&(1<<(j-1)))&&j!=fi)
32                 {
33                     p=i^(1<<(j-1));
34                     for(k=1;k<=n;k++)
35                         if((p&(1<<(k-1)))&&ok[k][j])
36                         {
37                             ans[i][j]+=ans[p][k];
38                         }
39                     if(ok[j][fi]&&pp>2)    anss+=ans[i][j];
40                 }
41             
42         }
43     }
44     printf("%lld",anss/2);
45     return 0;
46 }
47 /*
48 http://blog.csdn.net/fangzhenpeng/article/details/49078233
49 http://blog.csdn.net/tobewhatyouwanttobe/article/details/38036129
50 http://blog.csdn.net/kk303/article/details/9621933
51 http://blog.csdn.net/dreamon3/article/details/51347151
52 */

稍稍改進了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL n,m;
 7 bool ok[30][30];
 8 LL ans[1000000][22];
 9 LL anss;
10 int main()
11 {
12     LL a,b,i,j,k,fi,p,pp;
13     scanf("%lld%lld",&n,&m);
14     for(i=1;i<=m;i++)
15     {
16         scanf("%lld%lld",&a,&b);
17         ok[a][b]=ok[b][a]=true;
18     }
19     for(i=1;i<(1<<n);i++)
20     {
21         pp=__builtin_popcountll(i);
22         fi=__builtin_ffsll(i);
23         if(pp==1)
24             ans[i][fi]=1;
25         else
26         {
27             for(j=fi+1;j<=n;j++)
28                 if((i&(1<<(j-1))))
29                 {
30                     p=i^(1<<(j-1));
31                     for(k=1;k<=n;k++)
32                         if((p&(1<<(k-1)))&&ok[k][j])
33                             ans[i][j]+=ans[p][k];
34                     if(ok[j][fi]&&pp>2)    anss+=ans[i][j];
35                 }
36             
37         }
38     }
39     printf("%lld",anss/2);
40     return 0;
41 }
42 /*
43 http://blog.csdn.net/fangzhenpeng/article/details/49078233
44 http://blog.csdn.net/tobewhatyouwanttobe/article/details/38036129
45 http://blog.csdn.net/kk303/article/details/9621933
46 http://blog.csdn.net/dreamon3/article/details/51347151
47 */