借助树的概率dp(期望)+数学-好题-hdu-4035-Maze
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4035
题目意思：
有n个房间，有n-1条通道连接这n个房间（每两个房间之间有且只有一条路，所以实际上就是一棵树），在每个房间中，有三种选择要么被杀则回到第一个房间，概率为ki,要么从出口逃离概率为ei,要么通过通道到达其他的房间。
解题思路：
好题。
状态转移方程很好想，但是求的时候有技巧，不能直接用高斯消元来求（n有10000）肯定会超时。发现知，此题是在一棵树上转移，所以可以借助树的特点，分成两部分儿子和父亲，抽象出系数，然后从叶子节点向上求出父亲节点。
以下文字选自http://blog.csdn.net/morgan_xww/article/details/6776947
设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。
叶子结点：
E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);
= ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);
非叶子结点：（m为与结点相连的边数）
E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );
= ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);
设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;
对于非叶子结点i，设j为i的孩子结点，则
∑(E[child[i]]) = ∑E[j]
= ∑(Aj*E[1] + Bj*E[father[j]] + Cj)
= ∑(Aj*E[1] + Bj*E[i] + Cj)
带入上面的式子得
(1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj;
由此可得
Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj);
Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj);
Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj);
对于叶子结点
Ai = ki;
Bi = 1 - ki - ei;
Ci = 1 - ki - ei;
从叶子结点开始，直到算出 A1,B1,C1;
E[1] = A1*E[1] + B1*0 + C1;
所以
E[1] = C1 / (1 - A1);
若 A1趋近于1则无解...
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#define eps 1e-9#define INF 0x3fffffff#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 10100int deg[Maxn],cnt,n;double A[Maxn],B[Maxn],C[Maxn]; //分别表示系数double k[Maxn],e[Maxn];//表示被杀和逃离概率struct Edge{ int v; struct Edge * next;}edge[Maxn<<1],*head[Maxn<<1];void add(int a,int b){ ++cnt; deg[a]++; //度数 edge[cnt].v=b,edge[cnt].next=head[a]; head[a]=&edge[cnt];}void dfs(int cur,int pre){ struct Edge * p=head[cur]; bool flag=true; double suma=0,sumb=0,sumc=0; while(p) { int v=p->v; if(v!=pre) { flag=false; //不是叶子节点 dfs(v,cur);suma+=A[v];sumb+=B[v];sumc+=C[v]; } //求出儿子节点的各和 p=p->next; } if(flag) //叶子节点 { double t=1-k[cur]-e[cur]; A[cur]=k[cur],B[cur]=t,C[cur]=t; return ; }//非叶子节点 double temp=(1-k[cur]-e[cur])/deg[cur]; double tt=1-temp*sumb; A[cur]=(k[cur]+temp*suma)/tt; B[cur]=temp/tt; C[cur]=(temp*sumc+(1-k[cur]-e[cur]))/tt; return ;}int main(){ int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { scanf("%d",&n); memset(head,NULL,sizeof(head)); memset(deg,0,sizeof(deg)); cnt=0; for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } for(int i=1;i<=n;i++) { double a,b; scanf("%lf%lf",&a,&b); k[i]=a/100.0,e[i]=b/100.0; } dfs(1,-1); printf("Case %d: ",ca); if(fabs(1-A[1])<eps) //这里卡精度 printf("impossible\n"); else printf("%.5f\n",C[1]/(1.0-A[1])); } return 0;}