HDU4035 Maze(期望DP)

题意

抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

Sol

非常nice的一道题。

我简单的说一下思路：首先列出方程，$f[i]$表示在第$i$个位置走出迷宫的期望步数。

转移方程分叶子节点和父亲节点讨论一下，发现都可以化成$f[x] = a f[1] + b f[fa] + c$的形式

然后直接递推系数即可

具体可以看https://www.cnblogs.com/Paul-Guderian/p/7624039.html

/*

*/

#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 + , INF = 1e9 + ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 ;

    else return ;

}

void init() {

    for(int i = ; i <= N; i++) v[i].clear();

}

double Get(int x) {

    return ( - b[x] - e[x]) / (v[x].size());

}

bool dfs(int x, int fa) {

    if(v[x].size() ==  && (v[x][] == fa)) {A[x] = b[x], C[x] = B[x] = Get(x); return ;}

    double As = , Bs = , Cs = ;

    for(int i = ; i < v[x].size(); i++) {

        int to = v[x][i];

        if(to == fa) continue;

        if(!dfs(to, x)) return ;

        As += A[to]; Bs += B[to]; Cs += C[to] + ;

    }

    double P = Get(x);

    double D = ( - Bs * P);

    if(!dcmp(D)) return ;

    A[x] = (b[x] + As * P) / D;

    B[x] = P / D;

    C[x] = (Cs * P + ((x == ) ?  : P)) / D;

    return ;

}

int main() {

    int T = read();

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

        N = read(); init();

        //printf("%d ", v[3].size());

        for(int i = ; i <= N - ; i++) {

            int x = read(), y = read();

            v[x].push_back(y); v[y].push_back(x);

        }

        for(int i = ; i <= N; i++) b[i] = (double) read() / , e[i] = (double) read() / ;

        if(dfs(, ) && (dcmp( - A[]))) printf("Case %d: %.10lf\n", GG, C[] / ( - A[]));

        else printf("Case %d: impossible\n", GG);

    }

    return ;

}

/*

*/