dp求期望的题。
题意：
有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，
从结点1出发，开始走，在每个结点i都有3种可能：
1.被杀死，回到结点1处（概率为ki）
2.找到出口，走出迷宫 （概率为ei）
3.和该点相连有m条边，随机走一条
求：走出迷宫所要走的边数的期望值。
设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。
叶子结点：
E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);//因为是到达，i点跑出去的期望步数，所以逃出去的那个概率应该乘以0
= 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则无解...
上面这一问题，中发现E[1]消不去，然后就用算出A,B,C的方式来求解。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<cmath>
6 #include<vector>
7 using namespace std;
8 const int MAXN=10007;
9 const double eps=1e-10;//这里1e-8会WA。设为1e-9和1e-10可以
10 double k[MAXN],e[MAXN];
11 double A[MAXN],B[MAXN],C[MAXN];
12
13 int T,n,u,v,iCase;
14 vector<int>vec[MAXN];//存树
15
16 bool dfs(int t,int pre)//t的根结点是pre
17 {
18 int m=vec[t].size();//点t的度
19 A[t]=k[t];
20 B[t]=(1-k[t]-e[t])/m;
21 C[t]=1-k[t]-e[t];
22 double tmp=0;
23 for(int i=0;i<m;i++)
24 {
25 int v=vec[t][i];
26 if(v==pre)continue;
27 if(!dfs(v,t))return false;
28 A[t]+=(1-k[t]-e[t])/m*A[v];
29 C[t]+=(1-k[t]-e[t])/m*C[v];
30 tmp+=(1-k[t]-e[t])/m*B[v];
31 }
32 if(fabs(tmp-1)<eps)return false;
33 A[t]/=(1-tmp);
34 B[t]/=(1-tmp);
35 C[t]/=(1-tmp);
36 return true;
37 }
38 int main()
39 {
40 scanf("%d",&T);
41 while(T--)
42 {
43 iCase++;
44 scanf("%d",&n);
45 for(int i=1;i<=n;i++)vec[i].clear();
46 for(int i=1;i<n;i++)
47 {
48 scanf("%d%d",&u,&v);
49 vec[u].push_back(v);
50 vec[v].push_back(u);
51 }
52 for(int i=1;i<=n;i++)
53 {
54 scanf("%lf%lf",&k[i],&e[i]);
55 k[i]/=100;
56 e[i]/=100;
57 }
58 printf("Case %d: ",iCase);
59 if(dfs(1,-1)&&fabs(1-A[1])>eps)
60 {
61 printf("%.6lf
",C[1]/(1-A[1]));
62 }
63 else printf("impossible
");
64 }
65 }