HDU 4035 期望dp

这道题站在每个位置上都会有三种状态

死亡回到起点:k[i]

找到出口结束 e[i]

原地不动 p[i]

k[i]+e[i]+p[i] =1;

因为只给了n-1条路把所有都连接在一起，那么我们可以自然的把这张图看成一个树型结构

根据作为父亲节点和叶子节点作为区分

进行推导

详情可参考:http://blog.csdn.net/morgan_xww/article/details/6776947/

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 #define N 10005

 #define del 1e-10

 vector <int> G[N];

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

 int n;

 bool solve(int u,int fa)

 {

     A[u] = k[u];

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

     C[u] = p[u];

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

         return true;

     double tmp = ;

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

         int j = G[u][i];

         if(j!=fa)

         {

             //既是一个判断过程也是一个找叶子节点的过程，先做递归是为了先更新好叶子节点作为底层的信息，

             //用以推得上层信息

             if(!solve(j,u))

                 return false;

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

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

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

         }

     }

     tmp = -tmp;

     if(tmp < del)

         return false;

     A[u] /= tmp;

     B[u] /= tmp;

     C[u] /= tmp;

     return true;

 }

 int main()

 {

     int T,a,b,c,d;

     scanf("%d",&T);

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

         scanf("%d",&n);

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

             G[i].clear();

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

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

             G[a].push_back(b);

             G[b].push_back(a);

         }

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

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

             k[i] = c*1.0/;

             e[i] = d*1.0/;

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

         }

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

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

             printf("impossible\n");

             continue;

         }

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

     }

 }