BZOJ 3566 - [SHOI2014]概率充电器

Published on 2016-11-28

描述

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器：“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器,您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”
SHOI 概率充电器由 $n - 1$ 条导线连通了 $n(n\le 500000)$ 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

分析

根据期望的线性性质，答案等于每个元件进入充电状态的概率。由于只需要有一个条件满足，这个元件就有电，这是“或”的关系，考虑到概率中一般求“与”比较容易，我们考虑求每个元件没被充电的概率。
首先将树转换为有根树，设 $f_i$ 为节点 $i$ 没有不被自己及子树充电的概率， $g_i$ 为不被自己父亲充电的概率（ $g_i$ 这个状态假定自己不直接通电）。我们首先考虑算 $f_i$ 。

设 $Q_i$ 为节点 $i$ 直接通电的概率， $P_{i, j}$ 为边 $(i, j)$ 通电的概率。
要满足一个节点 $i$ 不被自己以及自己的子树充电，那么首先自己不能有电，概率为 $1 - Q_i$ ，接着对于每一个儿子，要么儿子没有电，要么儿子有电但是连接自己以及儿子的边没有电，所以：

f_i = (1 - Q_i)\prod_{j\in \mathrm{sons}(i)}f_j + (1 - f_j)(1 - P_{i, j})

接着考虑如何算不被父亲充电的概率，对于根节点 0 来说， $g_0 = 1$ 。接着我们考虑非根节点 $i$ 不被父亲充电的概率。还是分为两种情况，要么父亲没有电，要么父亲有电但是连接父亲的边没有电。我们先求父亲 $\mathrm{fa}(i)$ 没有电的概率 $P'$ 。父亲没有电，说明子树没有传电给父亲而且父亲的父亲没有传电。由于我们已经假定了 $i$ 不直接通电，所以我们应该去除 $i$ 对 $\mathrm{fa}(i)$ 的影响，这样就能算出 $\mathrm{fa}(i)$ 没有电的概率了：

P' = g_{\mathrm{fa}(i)}\cdot\frac {f_{\mathrm{fa}(i)}}{f_i + (1 - f_i)(1 - P_{i, \mathrm{fa}(i)})}

所以可以根据 $P'$ 算出 $g_i$ 来：

g_i = P' + (1 - P')(1 - P_{i, \mathrm{fa}(i)})

每个节点不通电的概率是 $f_i\cdot g_i$ ，所以答案就是：

\sum_{1\le i\le n}1 - f_i\cdot g_i

复杂度： $O(n)$ 。

代码

//  Created by Sengxian on 2016/11/28.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3566 树形概率 DP 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 500000 + 3;

struct edge {
    edge *next;
    int to, p;
    edge(edge *next = NULL, int to = 0, int p = 0): next(next), to(to), p(p) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];
int n, q[MAX_N], fv[MAX_N];
double f[MAX_N], g[MAX_N];

void dfs1(int u, int fa) {
    f[u] = (100 - q[u]) / 100.0;
    for (edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        fv[e->to] = e->p;
        dfs1(e->to, u);
        f[u] *= f[e->to] + (1 - f[e->to]) * ((100 - e->p) / 100.0);
    }
}

void dfs2(int u, int fa) {
    if (fa == -1) g[u] = 1.0;
    else {
        double t = g[fa] * f[fa] / (f[u] + (1 - f[u]) * ((100 - fv[u]) / 100.0));
        g[u] = t + (1 - t) * ((100 - fv[u]) / 100.0);
    }

    for (edge *e = first[u]; e; e = e->next) if (e->to != fa)
        dfs2(e->to, u);
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt();
    for (int i = 0, u, v, p; i < n - 1; ++i) {
        u = readInt() - 1, v = readInt() - 1, p = readInt();
        first[u] = new (pit++) edge(first[u], v, p);
        first[v] = new (pit++) edge(first[v], u, p);
    }
    for (int i = 0; i < n; ++i) q[i] = readInt();

    dfs1(0, -1), dfs2(0, -1);

    double ans = 0;
    for (int i = 0; i < n; ++i) ans += 1 - f[i] * g[i];
    printf("%.6f\n", ans);
    return 0;
}

BZOJ 1426 - 收集邮票 BZOJ 3450 - Tyvj1952 Easy

Sengxian's Blog

BZOJ 3566 - [SHOI2014]概率充电器

描述

分析

代码