# Hdu4035 maze (expected DP)

## meaning of the title

Copied from https://www.cnblogs.com/Paul-Guderian/p/7624039.html

There are n rooms connected by n-1 tunnels to form a tree. Starting from node 1, start walking. There are three possibilities (the sum of probabilities is 1) at each node i: 1. Be killed and return to node 1 (the probability is ki); 2. Find the exit and walk out of the maze (the probability is ei)
3. There are m edges connected with the point, and randomly walk one to find the expected number of edges to walk out of the maze. (2≤n≤10000)

## Sol

A very nice question.

Let me just say something simple: first, list the equations, \$f[i] \$represents the expected steps out of the maze at \$I \$.

The transfer equation can be divided into leaf node and parent node. It is found that they can be reduced to the form of \$f[x] = a f[1] + b f[fa] + c \$

Then the direct recurrence coefficient can

See https://www.cnblogs.com/Paul-Guderian/p/7624039.html for details

```/*

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
const double eps = 1e-10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
vector<int> v[MAXN];
double b[MAXN], e[MAXN], A[MAXN], B[MAXN], C[MAXN];
bool dcmp(double x) {
if(fabs(x) < eps) return 0;
else return 1;
}
void init() {
for(int i = 1; i <= N; i++) v[i].clear();
}
double Get(int x) {
return (1 - b[x] - e[x]) / (v[x].size());
}
bool dfs(int x, int fa) {
if(v[x].size() == 1 && (v[x][0] == fa)) {A[x] = b[x], C[x] = B[x] = Get(x); return 1;}
double As = 0, Bs = 0, Cs = 0;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa) continue;
if(!dfs(to, x)) return 0;
As += A[to]; Bs += B[to]; Cs += C[to] + 1;
}
double P = Get(x);
double D = (1 - Bs * P);
if(!dcmp(D)) return 0;
A[x] = (b[x] + As * P) / D;
B[x] = P / D;
C[x] = (Cs * P + ((x == 1) ? 0 : P)) / D;
return 1;
}
int main() {
for(int GG = 1; GG <= T; GG++) {
//printf("%d ", v[3].size());
for(int i = 1; i <= N - 1; i++) {
v[x].push_back(y); v[y].push_back(x);
}
for(int i = 1; i <= N; i++) b[i] = (double) read() / 100, e[i] = (double) read() / 100;
if(dfs(1, 0) && (dcmp(1 - A[1]))) printf("Case %d: %.10lf\n", GG, C[1] / (1 - A[1]));
else printf("Case %d: impossible\n", GG);
}
return 0;
}
/*

*/```

Keywords: C++

Added by krellen on Thu, 02 Jan 2020 04:23:44 +0200