题意
一个人被丢进了迷宫， 迷宫有n个房间，1号房间作为起点，房间之间以隧道联通，任意两个房间的通路只有一条，每进入一个房间，有k的概率被干掉，然后在1号房间复活，有e的概率直接脱出迷宫，若上述两事件未发生，则这个人会从当前房间的全部隧道中随便选一个进去（即使沿着刚才的路返回）。问你这个人要穿过多少隧道才能拖出迷宫（求期望）。
思路
注意审题，“任意两个房间的通路只有一条” ，这句话告诉我们迷宫可以抽象为一棵树（因为没有环，起点确定所以看作树根），又因为是求期望，所以这是一个树上进行的概率dp。
对于每个节点，我们定义dp数组为dp[i]表示在i号房间脱出迷宫的期望穿洞数。
接下来就是处理dp方程，如果你可以写出来dp方程的话，你会发现这个方程有两种版本，一种是叶子节点，一种是普通节点（其实还有一种根节点，不过这个只是最后出答案用的），列完之后我们会发现dp方程组成环，而且每一个方程式都有着类似的未知项（或者说是格式统一），面对这种情况就可以归纳出方程的一般形式，建立几个系数数组，回代一般形式，确定出系数数组的递推关系式，化环为链。这种情形经常出现在概率dp问题中。
最后需要注意本题有坑点：判断误解的时候，需要直接判断1-A[1](这个是什么请看下面的数学推导）的绝对值是否非常小（分母趋向于0），在这里卡精度，你至少需要1e-9的精度。在这里用其他的方法判断一律是过不了的～
相关数学推导
以下内容引用自http://mlz000.logdown.com/posts/220880-hdu-4035-maze-probability-dp，谢谢！
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
// // HDU4035.cpp // playground // // Created by Adam Chang on 2015/4/5. // Copyright (c) 2015年 Adam Chang. All rights reserved. // //Review: Each pair of rooms is connected by one and only one path //this statement marks the structure is tree (or DAG),i.e. no rings. #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; struct vertexType{ vector<int> to; double pk,pe; void init(){ to.clear(); pk = 0; pe = 0; } } vertex[10005]; double A[10005],B[10005],C[10005]; bool vis[10005]; void dfs(int father){ vis[father] = true; vector<int> child; for (int i = 0; i < vertex[father].to.size(); i++) { int next = vertex[father].to[i]; if (vis[next]) { continue; } child.push_back(next); dfs(next); } double w = 1-vertex[father].pk-vertex[father].pe; if (child.size()) { //normal vertex double m = (double)vertex[father].to.size(); double q = 1; double e = vertex[father].pk; double r = w; for (int i = 0; i < child.size(); i++) { e += w/m*A[child[i]]; q -= w/m*B[child[i]]; r += w/m*C[child[i]]; } A[father] = e/q; B[father] = w/m/q; C[father] = r/q; }else{ //endpoint vertex A[father] = vertex[father].pk; B[father] = w; C[father] = w; } } int main(){ int caseCnt; scanf(" %d",&caseCnt); for (int ci = 1; ci <= caseCnt; ci++) { int n = 0; scanf(" %d",&n); for (int i = 1; i <= n; i++) { vertex[i].init(); } for (int i = 1; i <= n-1; i++) { int arg1,arg2; scanf(" %d %d",&arg1,&arg2); vertex[arg1].to.push_back(arg2); vertex[arg2].to.push_back(arg1); } for (int i = 1; i <= n; i++) { double arg1,arg2; scanf(" %lf %lf",&arg1,&arg2); vertex[i].pk = arg1/100; vertex[i].pe = arg2/100; } memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); memset(C, 0, sizeof(C)); memset(vis, 0, sizeof(vis)); dfs(1); if (abs(1-A[1]) < 0.000000001) {//这里卡精度 printf("Case %d: impossible\n",ci); continue; } printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1])); } return 0; } |
