Maze （HDU

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4035

题解：

　　一道经典的循环期望，难点在于公式的推导。

　　推导太复杂，看着题解都推了好久，不想再用公式编辑器写一遍了，想看的点这里。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define LL long long
 7 #define RI register int
 8 #define eps 1e-10
 9 using namespace std;
10 const int INF = 0x7ffffff ;
11 const int N = 10000 + 10 ;
12 const int M = 1e7 + 10 ;
13 
14 inline int read() {
15     int k = 0 , f = 1 ; char c = getchar() ;
16     for( ; !isdigit(c) ; c = getchar())
17       if(c == '-') f = -1 ;
18     for( ; isdigit(c) ; c = getchar())
19       k = k*10 + c-'0' ;
20     return k*f ;
21 }
22 struct Edge {
23     int to, next ;
24 }ee[M] ;
25 int n, cnt = 0 ; int head[N] ; double k[N], e[N], A[N], B[N], C[N], in[N] ;
26 inline void add_edge(int x,int y) {
27     ee[++cnt].to = y, ee[cnt].next = head[x], head[x] = cnt ;
28 }
29 
30 void dfs(int x,int f) {
31     A[x] = k[x]*in[x], B[x] = 1.0-k[x]-e[x], C[x] = (1-k[x]-e[x])*in[x] ; double fm = in[x] ;
32     for(int i=head[x];i;i=ee[i].next) {
33         int y = ee[i].to ; if(y == f) continue ;
34         dfs(y,x) ;
35         A[x] += B[x]*A[y] ; C[x] += B[x]*C[y] ; fm -= B[x]*B[y] ;
36     }
37     A[x] /= fm, B[x] /= fm, C[x] /= fm ;
38 }
39 inline void solve(int w) {
40     n = read() ; memset(head,0,sizeof(head)) ; memset(in,0,sizeof(in)) ; cnt = 0 ;
41     for(int i=1;i<n;i++) {
42         int x = read(), y = read() ; in[x]++, in[y]++ ;
43         add_edge(x,y) ; add_edge(y,x) ;
44     }
45     for(int i=1;i<=n;i++) k[i] = (double)read()/100.0, e[i] = (double)read()/100.0 ;
46     dfs(1,0) ;
47     double ans = C[1]/(1.0-A[1]) ;
48     printf("Case %d: ",w) ; 
49     if(abs(A[1]-1.0) < eps) printf("impossible
") ;
50     else printf("%.6lf
",ans) ;
51 }
52 
53 int main() {
54     int t = read() ;
55     for(int w=1;w<=t;w++) solve(w) ;
56     return 0 ;
57 }

另：

这题精度一定要开够，一开始开了1e-5 WA了，看别人博客发现也有人遇到了同样的问题=-=，开到1e-10即可。
库中有的函数不要自己写（尤其是与库中函数同名）。一开始没加cmath库，自己写了个abs（）函数，疯狂CE =-=