Codeforces 11 D. A Simple Task
問題
n個の頂点およびm本の辺からなる無向グラフが与えられる。
このグラフに含まれる閉路の個数を求めよ。
制約条件
n≦19
方針
まずは頂点0を含む閉路を考える。
これはdp[pos][mask]を、現在posにいて、今までmaskで表される集合の点を訪問する場合の数とする。
これをループをまわして、
頂点0から頂点0へ移動する経路の数を数える。
次に、グラフから頂点0を削除し、
頂点1を含む閉路をDPでと同様に数えて足す。
頂点1を削除して……と同様に繰り返す。
右回りと左回りで同じ閉路が二回数えられているので最後に2で割る。
ソースコード
int n,m; bool e[20][20]; ll dp[20][1<<20],ans; void run(){ cin>>n>>m; memset(e,0,sizeof(e)); rep(i,m){ int a,b; cin>>a>>b; a--; b--; e[a][b]=e[b][a]=1; } ans=0; for(int s=n-1;s>1;s--){ rep(i,s+1)rep(j,1<<s+1)dp[i][j]=0; dp[s][0]=1; rep(mask,1<<s+1)rep(i,s+1)rep(j,s+1)if(e[i][j]&&!(mask&1<<j)){ dp[j][mask|1<<j]+=dp[i][mask]; } rep(i,1<<s+1)if(__builtin_popcount(i)>2)ans+=dp[s][i]; } cout<<ans/2<<endl; }