hdu4035_概率dp

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4035
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); = 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则无解...
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <queue>
10 #include <vector>
11 using namespace std; 
12 
13 const int N = 10000 + 10;
14 double e[N], k[N], a[N], b[N], c[N];
15 vector <int> v[N];
16 bool find(int i, int fa)
17 {
18     if(v[i].size() == 1 && fa != -1)
19     {
20         a[i] = k[i];
21         b[i] = 1 - k[i] - e[i];
22         c[i] = 1 - k[i] - e[i];
23         return true;
24     }
25     a[i] = k[i];
26     b[i] = (1 - k[i] - e[i]) / v[i].size();
27     c[i] = 1 - k[i] - e[i];
28     double temp = 0;
29     for(int j = 0; j < (int)v[i].size(); j++)
30     {
31         if(v[i][j] == fa)
32             continue;
33         if(!find(v[i][j], i))
34             return false;
35         a[i] += b[i] * a[v[i][j]];
36         c[i] += b[i] * c[v[i][j]];
37         temp += b[i] * b[v[i][j]];
38     }
39     if(fabs(1 - temp) < 1e-10)
40         return false;
41     a[i] /= (1 - temp);
42     b[i] /= (1 - temp);
43     c[i] /= (1 - temp);
44     return true;
45 }
46 int main()
47 {
48     int t, n, x, y, cnt = 0;
49     scanf("%d", &t);
50     while(t--)
51     {
52         cnt++;
53         scanf("%d", &n);
54         for(int i = 1; i <= n; i++)
55             v[i].clear();
56         for(int i = 1; i < n; i++)
57         {
58             scanf("%d %d", &x, &y);
59             v[x].push_back(y);
60             v[y].push_back(x);
61         }
62         for(int i = 1; i <= n; i++){
63             scanf("%lf %lf", k + i, e + i);
64             k[i] /= 100.0;
65             e[i] /= 100.0;
66         }
67         cout << "Case " << cnt << ": "<<endl;
68         if(find(1, -1) && 1 - a[1] > 1e-10)
69             printf("%.6lf
", c[1]/(1 - a[1]));
70         else
71             cout << "impossible" << endl;
72     }
73     return 0;
74 }
View Code
原文地址:https://www.cnblogs.com/luomi/p/5695689.html