JAG冬コンテスト2012 Problem G Network Reliability (AOJ2345)
問題
無向グラフが与えられる。
それぞれの辺は、独立に確率P(全て等しい)で消滅する。
全ての辺について、消滅の判定が終わった後で、グラフが連結である確率を求めよ。
制約条件
グラフの頂点数≦14
辺の本数≦100
0≦P≦100
方針
動的計画法による。
dp[i]を、ビットであらわされる頂点集合iが連結である確率とする。
iが非連結になる場合は、
iの最小元を含むような部分集合sについて、sが連結で、sとs-iに一本も辺がない場合である。
したがってdp[i]=1-Σdp[s]*p^(sとs-iにある辺の本数)
の漸化式が成り立つ。
ソースコード
int n,m,a[100],b[100]; double dp[1<<14],p; int main(){ cin>>n>>m>>p; p/=100; rep(i,m)cin>>a[i]>>b[i], a[i]--, b[i]--; rep(i,1<<n)if(i){ int l=0; for(;!(l&i);l++); dp[i]=1; for(int s=i;s;s=s-1&i){ if(s==i||!(s&l))continue; double tmp=dp[s]; rep(j,m)if((i&1<<a[j])&&(i&1<<b[j])&&(s>>a[j]&1)!=(s>>b[j]&1))tmp*=p; dp[i]-=tmp; } } printf("%.12f\n",dp[(1<<n)-1]); return 0; }