Maze
HDU - 4035
题意：
有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\n",c[1]/(1-a[1]));else puts("impossible");}return 0; }