首页 > ACM题库 > HDU-杭电 > HDU 4035-Maze-动态规划-[解题报告]HOJ
2015
04-15

HDU 4035-Maze-动态规划-[解题报告]HOJ

Maze

问题描述 :

When wake up, lxhgww find himself in a huge maze.

The maze consisted by N rooms and tunnels connecting these rooms. Each pair of rooms is connected by one and only one path. Initially, lxhgww is in room 1. Each room has a dangerous trap. When lxhgww step into a room, he has a possibility to be killed and restart from room 1. Every room also has a hidden exit. Each time lxhgww comes to a room, he has chance to find the exit and escape from this maze.

Unfortunately, lxhgww has no idea about the structure of the whole maze. Therefore, he just chooses a tunnel randomly each time. When he is in a room, he has the same possibility to choose any tunnel connecting that room (including the tunnel he used to come to that room).
What is the expect number of tunnels he go through before he find the exit?

输入:

First line is an integer T (T ≤ 30), the number of test cases.

At the beginning of each case is an integer N (2 ≤ N ≤ 10000), indicates the number of rooms in this case.

Then N-1 pairs of integers X, Y (1 ≤ X, Y ≤ N, X ≠ Y) are given, indicate there is a tunnel between room X and room Y.

Finally, N pairs of integers Ki and Ei (0 ≤ Ki, Ei ≤ 100, Ki + Ei ≤ 100, K1 = E1 = 0) are given, indicate the percent of the possibility of been killed and exit in the ith room.

输出:

First line is an integer T (T ≤ 30), the number of test cases.

At the beginning of each case is an integer N (2 ≤ N ≤ 10000), indicates the number of rooms in this case.

Then N-1 pairs of integers X, Y (1 ≤ X, Y ≤ N, X ≠ Y) are given, indicate there is a tunnel between room X and room Y.

Finally, N pairs of integers Ki and Ei (0 ≤ Ki, Ei ≤ 100, Ki + Ei ≤ 100, K1 = E1 = 0) are given, indicate the percent of the possibility of been killed and exit in the ith room.

样例输入:

3
3
1 2
1 3
0 0
100 0
0 100
3
1 2
2 3
0 0
100 0
0 100
6
1 2
2 3
1 4
4 5
4 6
0 0
20 30
40 30
50 50
70 10
20 60

样例输出:

Case 1: 2.000000
Case 2: impossible
Case 3: 2.895522

题意:有很多个房间,你可以经过传送门,传送方法有三种,1:到达与这个房间相连的其他房间,2:kill,回到起点。3:出口,逃离这个空间。这三个的发生概率是不同的,求逃离的数学期望。

显然是dp,可惜我对不起林教,没有得其真传,然后去搜报告,结果还是林教的报告,写的很简单,但是很明了,和以前那题差不多,可惜这是在这颗树上。然后wa了10次,分析问题太不全面了,竟然认为每个节点的A,B,C是不变的。。。我汗啊,不知道当时我是怎么想的。

分析一下:首先,期望一般采用逆推,对于每个节点,有三种转移1:到达与这个房间相连的其他房间,2:kill,回到起点。3:出口,逃离这个空间。用p[i]表示距离出口还差多少期望。(因为是反过来的)显然p[1] 为最终的答案。

那么列出每个节点的期望转移。

先是叶子节点:p[i]=p[1]*k[i]+e[i]*0+(1-k[i]-e[i])*p[f[i]];(0是因为当前节点为出口时期望为0,看清楚p[i]的定义;f[i]表示i当前的父亲节点);

然后是非叶子节点p[i]=p[1]*k[i]+e[i]*0+(1-k[i]-e[i])/cnt*((sum(p[j])+1)+p[f[i]]+1);(j为儿子节点,cnt为与这个房间相连的房子总数);其实我觉得这个方程设定也很巧妙,为什么要分开成父亲节点和儿子节点呢?特别是下面的转换;

设p[i]满足p[i]=A[i]*p[1]+B[i]*p[f[i]]+C[i];然后代入,将p[j]换掉;

你会得到一个关于p[i],e1,p[f[i]],的方程,自己动手算算;

这里我只给出化简后的式子。

p[i]=(k[i]+(1-k[i]-e[i])/m*sum(A[j]))/(1-(1-k[i]-e[i])/m*sum(B[j]))*p[1]+(1-k[i]-e[i])/m)/(1-(1-k[i]-e[i])/m*sum(B[j]))*p[f[i]]+1-k[i]-e[i]+(1-k[i]-e[i])/m*sum(C[j]));

p[i]=A[i]*e1+B[i]*p[f[i]]+C[i]对比得出

A[i]=(k[i]+(1-k[i]-e[i])/m*sum(A[j]))/(1-(1-k[i]-e[i])/m*sum(B[j]));

B[i]=(1-k[i]-e[i])/m)/(1-(1-k[i]-e[i])/m*sum(B[j]));

C[i]=1-k[i]-e[i]+(1-k[i]-e[i])/m*sum(C[j]));

这样就差不多完工了,因为p[1]=A[1]*P[1]+B[1]*0+C[1];

得出p[1]=C[1]/(1-A[1]);你会发现所有的p[i]其实都是中间变量,到最后都没了,林教说一般都是这样子的。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4616318 2011-09-17 11:12:06 Accepted 4035 93MS 1020K 1658B C++ xym2010
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
    double e,k;
}d[10005];
struct egde
{
    int v,next;
}ee[20005];
double A[10005],B[10005],C[10005];
int n,fa[10005],pos=0,flag=1;
void DP(int t,int f)
{
    int cnt=0;
    if(ee[fa[t]].next==-1&&f!=-1)
    {
        A[t]=d[t].k;
        B[t]=1-d[t].k-d[t].e;
        C[t]=1-d[t].k-d[t].e;
        return ;
    }
	A[t]=0;B[t]=0;C[t]=0;
    for(int i=fa[t];i!=-1;i=ee[i].next)
    {
        cnt++;
        if(ee[i].v==f)continue;
        DP(ee[i].v,t);
        A[t]+=A[ee[i].v];
        B[t]+=B[ee[i].v];
        C[t]+=C[ee[i].v];
    }
    double tt=(1-d[t].k-d[t].e)/cnt;
    A[t]=(d[t].k+tt*A[t])/(1-tt*B[t]);
    C[t]=(1-d[t].k-d[t].e+tt*C[t])/(1-tt*B[t]);
    B[t]=(tt)/(1-tt*B[t]);
}
int main()
{
    int T,t,x,y,k,e;
    scanf("%d",&T);
    for(t=1;t<=T;t++)
    {
        memset(fa,-1,sizeof(fa));
        pos=0;flag=1;
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d",&x,&y);
            ee[pos].v=y;ee[pos].next=fa[x];fa[x]=pos++;
            ee[pos].v=x;ee[pos].next=fa[y];fa[y]=pos++;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&k,&e);
            d[i].e=e/100.0;
            d[i].k=k/100.0;
        }
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        DP(1,-1);
        printf("Case %d: ",t);
        if(fabs(1-A[1])<=1e-10)printf("impossible\n");
        else
            printf("%f\n",C[1]/(1-A[1]));
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xymscau/article/details/6785348


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。