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;
}