成都区域赛区Maze杭电4035(dp求期望)-白红宇

成都区域赛区Maze杭电4035(dp求期望)

阅读量：4129 次

发布时间：2019-05-25

本文共 2893 字，大约阅读时间需要 9 分钟。

解题思路分析过程转载：

02. dp求期望的题。

03. 题意：

04. 有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，

05. 从结点1出发，开始走，在每个结点i都有3种可能：

06. 1.被杀死，回到结点1处（概率为ki）

07. 2.找到出口，走出迷宫（概率为ei）

08. 3.和该点相连有m条边，随机走一条

09. 求：走出迷宫所要走的边数的期望值。

10.

11. 设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。

12.

13. 叶子结点：

14. E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);

15. = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);

16.

17. 非叶子结点：（m为与结点相连的边数）

18. E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );

19. = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);

20.

21. 设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;

22.

23. 对于非叶子结点i，设j为i的孩子结点，则

24. ∑(E[child[i]]) = ∑E[j]

25. = ∑(Aj*E[1] + Bj*E[father[j]] + Cj)

26. = ∑(Aj*E[1] + Bj*E[i] + Cj)

27. 带入上面的式子得

28. (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;

29. 由此可得

30. Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj);

31. Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj);

32. Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj);

33.

34. 对于叶子结点

35. Ai = ki;

36. Bi = 1 - ki - ei;

37. Ci = 1 - ki - ei;

38.

39. 从叶子结点开始，直到算出 A1,B1,C1;

40.

41. E[1] = A1*E[1] + B1*0 + C1;

42. 所以

43. E[1] = C1 / (1 - A1);

44. 若 A1趋近于1则无解...

45.**/

#include 
   
       #include 
    
        #include 
     
         #include 
      
           using namespace std;   const int MAXN = 10000 + 5;   double e[MAXN], k[MAXN];  double A[MAXN], B[MAXN], C[MAXN];   vector
       
         v[MAXN];   bool search(int i, int fa)  {      if ( v[i].size() == 1 && fa != -1 )      {          A[i] = k[i];          B[i] = 1 - k[i] - e[i];          C[i] = 1 - k[i] - e[i];          return true;      }       A[i] = k[i];      B[i] = (1 - k[i] - e[i]) / v[i].size();      C[i] = 1 - k[i] - e[i];      double tmp = 0;            for (int j = 0; j < (int)v[i].size(); j++)      {          if ( v[i][j] == fa ) continue;          if ( !search(v[i][j], i) ) return false;          A[i] += A[v[i][j]] * B[i];          C[i] += C[v[i][j]] * B[i];          tmp  += B[v[i][j]] * B[i];      }      if ( fabs(tmp - 1) < 1e-10 ) return false;      A[i] /= 1 - tmp;      B[i] /= 1 - tmp;      C[i] /= 1 - tmp;      return true;  }   int main()  {      int nc, n, s, t;    int i;    cin >> nc;      for (int ca = 1; ca <= nc; ca++)      {          cin >> n;          for (i = 1; i <= n; i++)              v[i].clear();           for ( i = 1; i < n; i++)          {              cin >> s >> t;              v[s].push_back(t);              v[t].push_back(s);          }          for ( i = 1; i <= n; i++)          {              cin >> k[i] >> e[i];              k[i] /= 100.0;              e[i] /= 100.0;         }                  cout << "Case " << ca << ": ";         if ( search(1, -1) && fabs(1 - A[1]) > 1e-10 )             cout << C[1]/(1 - A[1]) << endl;         else              cout << "impossible" << endl;      }      return 0;  }