skyaozoraの日記

問題概要

23:32

14頂点以下のグラフが与えられる。それぞれの辺は（独立に）p%の確率で消滅する時、残ったグラフが連結である確率を求めよ。

解法

23:32

ある頂点集合が連結である確率をbitDPで求める。求め方は、「その集合の中のindexが最小の要素を含む連結成分が集合より小さい」確率を求めて1から引く。その確率は、全ての（最小の要素を含み、元の集合よりは小さい）部分集合における「部分集合が連結である確率」*「部分集合が補集合と繋がっていない確率」の和。O(N^3*N)

//11年度冬コンテストF NetworkReliability (AOJ2345)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double dp[(1<<14)+10];
double pr[16][(1<<14)+10];
double gr[16][16];
int main()
{
	int n,m,p,a,b;
	rep(i,16) rep(j,16) gr[i][j]=0.0;
	cin>>n>>m>>p;
	rep(i,m){
		cin>>a>>b;a--;b--;gr[a][b]=gr[b][a]=0.01*(100-p);
	}
	rep(i,n) rep(j,(1<<n)){
		pr[i][j]=1.0;
		rep(k,n){
			if((j&(1<<k))) pr[i][j]*=1.0-gr[i][k];
		}
	}
	REP(i,1,(1<<n)){
		int lo;
		while(!(i&(1<<lo))) lo++;
		dp[i]=1.0;
		for(int j=i;j>0;j=((j-1)&i)){
			if(j==i || !(j&(1<<lo))) continue;
			double t=dp[j];
			rep(k,n){
				if((j&(1<<k)) || !(i&(1<<k))) continue;
				t*=pr[k][j];
			}
			dp[i]-=t;
		}
	}
	printf("%.12f\n",dp[(1<<n)-1]);
}