首页 > > 程序设计 > C/C++ >

A Simple Task CodeForces - 11D

2018-06-17 21:34:58来源：未知阅读 ()

题意：输出一个无向图的简单环数量。简单环指无重复边的环。保证图无重边自环。

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 */