Luogu 4284 [SHOI2014]概率充电器

BZOJ 3566

树形$dp$ + 概率期望。

每一个点的贡献都是$1$，在本题中期望就等于概率。

发现每一个点要通电会在下面三件事中至少发生一件：

1、它自己通电了。

2、它的父亲给它通电了。

3、它的儿子给它通电了。

那么我们设$f_i$表示它的父亲给它通电的概率，$g_i$表示它的子树中给它通电的概率，那么最后的答案$\sum_{i = 1}^{n}f_i + g_i - f_i * g_i = \sum_{i = 1}^{n}1 - (1 - f_i) * (1 - g_i)$。

感觉好麻烦，直接把$f_i$和$g_i$设成不通电的概率好了。

先考虑计算$g$。

假设每个点$i$自己通电的概率是$a_i$，一条连接着$x$和$y$的边通电的概率是$val(x, y)$，那么$g_x = (1 - a_x)\prod_{y \in son(x)}(g_y + (1 - g_y) * (1 - val(x, y)))$。

因为如果一个点不从自己的子树中得到电，那么它自己一定没有电，然后对于每一个儿子，要么不通电，要么通了电但是这条边是不通电的，电量传递不上来。

然后考虑计算$f$，对于一对父子关系的点$(x, y)$，我们发现要么$x$不带电，要么$x$带了电但是这条边传递不过来，那么$x$不带电的概率$P = \frac{f_x * g_x}{g_y + (1 - g_y) * (1 - val(x, y))}$，

这时候我们默认$y$是不带电的，但是我们在计算$g_x$的时候多算了$y$的贡献，所以要除掉，然后$f_y = P + (1 - P) * (1 - val(x, y))$。

时间复杂度$O(n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef double db;

const int N = 5e5 + ;

int n, tot = , head[N];

db a[N], f[N], g[N];

struct Edge {

    int to, nxt;

    db val;

} e[N << ];

inline void add(int from, int to, db val) {

    e[++tot].to = to;

    e[tot].val = val;

    e[tot].nxt = head[from];

    head[from] = tot;

}

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

void dfs1(int x, int fat) {

    g[x] =  - a[x];

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fat) continue;

        dfs1(y, x);

        g[x] *= (g[y] + ( - g[y]) * ( - e[i].val));

    }

}

void dfs2(int x, int fat, int inEdge) {

    if(!fat) f[x] = 1.0;

    else {

        db p = g[fat] * f[fat] / (g[x] + ( - g[x]) * ( - e[inEdge].val));

        f[x] = p + ( - p) * ( - e[inEdge].val);

    }

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fat) continue;

        dfs2(y, x, i);

    }

}

int main() {

//    freopen("2.in", "r", stdin);

    read(n);

    for(int x, y, v, i = ; i < n; i++) {

        read(x), read(y), read(v);

        db val = 1.0 * v / 100.0;

        add(x, y, val), add(y, x, val);

    }

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

        int v; read(v);

        a[i] = 1.0 * v / 100.0;

    }

    dfs1(, );

    dfs2(, , );

/*    for(int i = 1; i <= n; i++)

        printf("%f ", f[i]);

    printf("\n");

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

        printf("%f ", g[i]);

    printf("\n");    */

    db ans = ;

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

        ans += ( - g[i] * f[i]);

    printf("%.6f\n", ans);

    return ;

}

巴特西

Luogu 4284 [SHOI2014]概率充电器

最新文章

热门文章