Maze
题意:
有n个房间,由n-1条隧道连通起来,实际上就形成了一棵树,从结点1出发,开始走,在每个结点i都有3种可能:
1.被杀死,回到结点1处(概率为ki)
2.找到出口,走出迷宫(概率为ei)
3.和该点相连有m条边,随机走一条
求:走出迷宫所要走的边数的期望值。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define maxn 10005 using namespace std; double E[maxn],K[maxn],a[maxn],b[maxn],c[maxn]; int T,n,num,head[maxn],du[maxn]; struct node{int to,pre;}e[maxn*2]; void Insert(int from,int to){ e[++num].to=to; e[num].pre=head[from]; head[from]=num; } bool search(int i,int fa){ if(du[i]==1&&fa!=-1){ a[i]=K[i]; b[i]=1-K[i]-E[i]; c[i]=1-K[i]-E[i]; return 1; } a[i]=K[i]; b[i]=(1-K[i]-E[i])/du[i]; c[i]=1-K[i]-E[i]; double tmp=0; for(int j=head[i];j;j=e[j].pre){ int to=e[j].to; if(to==fa)continue; if(!search(to,i))return 0; a[i]+=a[to]*b[i]; c[i]+=c[to]*b[i]; tmp+=b[to]*b[i]; } if(fabs(tmp-1)<1e-10)return 0; a[i]/=1-tmp; b[i]/=1-tmp; c[i]/=1-tmp; return 1; } int main(){ freopen("Cola.txt","r",stdin); scanf("%d",&T); int x,y; for(int Case=1;Case<=T;Case++){ printf("Case %d: ",Case); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); memset(du,0,sizeof(du)); num=0; scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); Insert(x,y);Insert(y,x); du[x]++;du[y]++; } for(int i=1;i<=n;i++){ scanf("%lf%lf",&K[i],&E[i]); K[i]/=100.0;E[i]/=100.0; } if(search(1,-1)&&fabs(1-a[1])>1e-10) printf("%.6lf ",c[1]/(1-a[1])); else puts("impossible"); } return 0; }