2015
04-15

# 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

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]));

 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;
}


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。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。