HDU 4035 Maze——概率dp

HDU 4035 Maze——概率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则无解...

#include #include #include #include #include #include using namespace std;const int maxn = 1e4 + 10;const double eps = 1e-10;int T, n;double k[maxn], e[maxn], a[maxn], b[maxn], c[maxn];vector G[maxn];bool dfs(int u, int f) { int m = G[u].size(); a[u] = k[u]; b[u] = (1-k[u]-e[u])/m; c[u] = 1-k[u]-e[u]; double temp = 0; for (int i = 0; i < m; i++) { int v = G[u][i]; if (v == f) continue; if (!dfs(v, u)) return false; a[u] += (1-k[u]-e[u])/m*a[v]; c[u] += (1-k[u]-e[u])/m*c[v]; temp += (1-k[u]-e[u])/m*b[v]; } if (fabs(1-temp) < eps) return false; a[u] /= (1-temp); b[u] /= (1-temp); c[u] /= (1-temp); return true;}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); for (int i = 0; i <= n; i++) G[i].clear(); int x, y; for (int i = 1; i < n; i++) { scanf("%d%d", &x, &y); G[x].push_back(y); G[y].push_back(x); } for (int i = 1; i <= n; i++) { scanf("%lf%lf", &k[i], &e[i]); k[i] /= 100.0; e[i] /= 100.0; } printf("Case %d: ", kase); if (dfs(1, -1) && fabs(1-a[1]) > eps) printf("%.6f\n", c[1]/(1-a[1])); else printf("impossible\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。