HDU 4035期待dp

この問題は位置ごとに3つの状態がある.
死は起点に戻る:k[i]
出口を見つけて終了e[i]
その場で動かないp[i]
k[i]+e[i]+p[i] =1;
 
n-1本の道だけがすべてをつなぐので、自然にこの図を木の構造と見ることができます.
親ノードとして葉ノードとして区別する
導き出す
 
詳細は、http://blog.csdn.net/morgan_xww/article/details/6776947/を参照してください.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <vector>

 4 using namespace std;

 5 #define N 10005

 6 #define del 1e-10

 7 vector <int> G[N];

 8 double A[N],B[N],C[N],k[N],e[N],p[N];

 9 int n;

10 bool solve(int u,int fa)

11 {

12     A[u] = k[u];

13     B[u] = p[u] / G[u].size();

14     C[u] = p[u];

15 

16     if(G[u].size() == 1 && fa!=0)

17         return true;

18 

19     double tmp = 0;

20     for(int i=0;i<G[u].size();i++){

21         int j = G[u][i];

22         if(j!=fa)

23         {

24             //                    ，                      ，

25             //        

26             if(!solve(j,u))

27                 return false;

28             A[u]+=B[u]*A[j];

29             C[u]+=B[u]*C[j];

30             tmp +=B[u]*B[j];

31         }

32     }

33 

34     tmp = 1-tmp;

35     if(tmp < del)

36         return false;

37 

38     A[u] /= tmp;

39     B[u] /= tmp;

40     C[u] /= tmp;

41 

42     return true;

43 }

44 

45 int main()

46 {

47     int T,a,b,c,d;

48     scanf("%d",&T);

49     for(int kase=1;kase<=T;kase++){

50         scanf("%d",&n);

51 

52         for(int i=1;i<=n;i++)

53             G[i].clear();

54 

55         for(int i=1;i<n;i++){

56             scanf("%d%d",&a,&b);

57             G[a].push_back(b);

58             G[b].push_back(a);

59         }

60         for(int i=1;i<=n;i++){

61             scanf("%d%d",&c,&d);

62             k[i] = c*1.0/100;

63             e[i] = d*1.0/100;

64             p[i] = 1-k[i]-e[i];

65         }

66 

67         printf("Case %d: ",kase);

68 

69         if(!solve(1,0) || 1-A[1]<del){

70             printf("impossible
");

71             continue;

72         }

73 

74         printf("%.6f
",C[1] / (1-A[1]));

75     }

76 }