A Simple Task CodeForces - 11D

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

ans[i][j]表示"包含i中的点,以i中第一个点为起点,以j为终点"的路径条数。

对于某个i,枚举当前终点j(显然不能是首个点),产生一个状态。再枚举上一次终点k,如果能转移就转移。

如果i中点数大于2且j到i中第一个点有路,就认为产生了环。最后每个环记录了两遍,要除以2。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m;
bool ok[][];
LL ans[][];
LL anss;
int main()
{
LL a,b,i,j,k,fi,p,pp;
scanf("%lld%lld",&n,&m);
for(i=;i<=m;i++)
{
scanf("%lld%lld",&a,&b);
ok[a][b]=ok[b][a]=true;
}
for(i=;i<(<<n);i++)
{
pp=__builtin_popcountll(i);
if(pp==)
{
//for(j=1;j<=n;j++)
ans[i][__builtin_ffsll(i)]=;
}
else
{
fi=__builtin_ffsll(i);
for(j=;j<=n;j++)
if((i&(<<(j-)))&&j!=fi)
{
p=i^(<<(j-));
for(k=;k<=n;k++)
if((p&(<<(k-)))&&ok[k][j])
{
ans[i][j]+=ans[p][k];
}
if(ok[j][fi]&&pp>) anss+=ans[i][j];
} }
}
printf("%lld",anss/);
return ;
}
/*
http://blog.csdn.net/fangzhenpeng/article/details/49078233
http://blog.csdn.net/tobewhatyouwanttobe/article/details/38036129
http://blog.csdn.net/kk303/article/details/9621933
http://blog.csdn.net/dreamon3/article/details/51347151
*/

稍稍改进了

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m;
bool ok[][];
LL ans[][];
LL anss;
int main()
{
LL a,b,i,j,k,fi,p,pp;
scanf("%lld%lld",&n,&m);
for(i=;i<=m;i++)
{
scanf("%lld%lld",&a,&b);
ok[a][b]=ok[b][a]=true;
}
for(i=;i<(<<n);i++)
{
pp=__builtin_popcountll(i);
fi=__builtin_ffsll(i);
if(pp==)
ans[i][fi]=;
else
{
for(j=fi+;j<=n;j++)
if((i&(<<(j-))))
{
p=i^(<<(j-));
for(k=;k<=n;k++)
if((p&(<<(k-)))&&ok[k][j])
ans[i][j]+=ans[p][k];
if(ok[j][fi]&&pp>) anss+=ans[i][j];
} }
}
printf("%lld",anss/);
return ;
}
/*
http://blog.csdn.net/fangzhenpeng/article/details/49078233
http://blog.csdn.net/tobewhatyouwanttobe/article/details/38036129
http://blog.csdn.net/kk303/article/details/9621933
http://blog.csdn.net/dreamon3/article/details/51347151
*/
05-11 18:03
查看更多