首页 > 代码库 > HDU 4035Maze（概率DP）
HDU 4035Maze（概率DP）
HDU 4035 Maze
体会到了状态转移，化简方程的重要性
题解转自http://blog.csdn.net/morgan_xww/article/details/6776947
/**
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 //#pragma comment(linker,"/STACK:102400000,102400000") 2 #include <map> 3 #include <set> 4 #include <stack> 5 #include <queue> 6 #include <cmath> 7 #include <ctime> 8 #include <vector> 9 #include <cstdio> 10 #include <cctype> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define INF 1e8 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, mid 19 #define rson k<<1|1, mid+1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FOPENIN(IN) freopen(IN, "r", stdin) 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } 31 32 //typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 10005; 35 const int MAXM = 100005; 36 const double eps = 1e-10; 37 //const LL MOD = 1000000007; 38 39 int T, N; 40 vector<int>v[MAXN]; 41 double k[MAXN], e[MAXN]; 42 double A[MAXN], B[MAXN], C[MAXN]; 43 44 45 void init() 46 { 47 int U, V; 48 scanf("%d", &N); 49 for(int i=0;i<=N;i++) v[i].clear(); 50 for(int i=0;i<N-1;i++) 51 { 52 scanf("%d %d", &U, &V); 53 v[U].push_back(V); 54 v[V].push_back(U); 55 } 56 for(int i=1;i<=N;i++) 57 { 58 scanf("%d %d", &U, &V); 59 k[i] = (double)U / 100.0; 60 e[i] = (double)V / 100.0; 61 } 62 } 63 64 bool DFS(int x, int fa) 65 { 66 A[x] = k[x]; 67 B[x] = (1 - k[x] - e[x]) / v[x].size(); 68 C[x] = 1 - k[x] - e[x]; 69 if(v[x].size() == 1 && x != fa) 70 return true; 71 double temp = 0; 72 for(int i = 0; i < v[x].size() ; i ++ ) 73 { 74 int y = v[x][i]; 75 if(y == fa) continue; 76 if(!DFS(y, x)) return false; 77 A[x] += A[y] * B[x]; 78 C[x] += C[y] * B[x]; 79 temp += B[y] * B[x]; 80 } 81 if(fabs(temp - 1.0) < eps) return false; 82 A[x] = A[x] / (1 - temp); 83 B[x] = B[x] / (1 - temp); 84 C[x] = C[x] / (1 - temp); 85 return true; 86 } 87 88 int main() 89 { 90 //FOPENIN("in.txt"); 91 scanf("%d", &T); 92 for(int t = 1; t <= T; t ++ ) 93 { 94 init(); 95 if( DFS(1, 1) && fabs(A[1] - 1.0) > eps ) 96 { 97 printf("Case %d: %lf\n", t, C[1] / (1 - A[1])); 98 } 99 else100 {101 printf("Case %d: impossible\n", t);102 }103 }104 }