bzoj3566

3566: [SHOI2014]概率充电器

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 982  Solved: 422
[Submit][Status][Discuss]

Description

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

Input

第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。

Output

输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数

Sample Input

3
1 2 50
1 3 50
50 0 0

Sample Output

1.000000

HINT

对于 100%的数据,n≤500000,0≤p,qi≤100。

Source

By 佚名提供

大家去看sengxian的博客 写的很详细 一般认真看就能懂了

正着做挺麻烦， 那么我们反着做

首先设f数组 f[u]表示u不被子树及自己充电的概率 怎么计算呢？

f[u] = f[u] * (1-q[u]) * (f[son[u]] + (1 - f[son[u]]) * (1 - p[e])) [son[u]是指每个儿子]

1-q[u]是指自己不直接被充电，f[son[u]]是指儿子不被子树充电，(1 - f[son[u]]) * (1 - p[e]) 是指儿子被充电了， 边没有充电

这里为什么不计算父亲带来的贡献呢？因为一会算父亲的贡献，乘上即可（自己理解，有误请指出）

设g[u]事不被父亲充电的概率

g[u] = g[u] * (P + (1 - P) * (1 - p[e])) 根上面一样 但是我们得算出P

P是指父亲不被充电的概率

P = g[fa] * f[fa] / (f[u] + (1 - f[u]) * (1 - p[e]))

这个除号是什么呢？因为我们已经知道u没有被充电，那么这里f[u]=0,所以应该忽略掉。因为上面对应的项是(f[son[u]] + (1 - f[son[u]]) * (1 - p[e]))，除去即可。

因为f[u]和g[u]都是不被充电的概率，那么期望就是sigma(1 - f[u] * g[u]) 不是很懂期望，学习一下。

#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
struct edge {
    int nxt, to; double p;
} e[N << 1];
int n, cnt = 1;
int head[N];
double p[N], f[N], g[N], q[N];
void link(int u, int v, int p)
{
    e[++cnt].nxt = head[u];
    head[u] = cnt;
    e[cnt].to = v;
    e[cnt].p = (double) p / 100;
}
void dfs1(int u, int last)
{
    f[u] = 1.0 - q[u];
    for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last)
    {
        dfs1(e[i].to, u); p[e[i].to] = e[i].p;
        f[u] *= f[e[i].to] + (1 - e[i].p) * (1 - f[e[i].to]);        
    }    
}
void dfs2(int u, int last)
{
    if(!last) g[u] = 1;
    else 
    {
        double t = g[last] * f[last] / (f[u] + (1 - f[u]) * (1 - p[u]));
        g[u] = t + (1 - t) * (1 - p[u]);
    }
    for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last)
        dfs2(e[i].to, u);    
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; ++i)
    {
        int u, v, p; scanf("%d%d%d", &u, &v, &p);
        link(u, v, p); link(v, u, p); 
    }
    for(int i = 1; i <= n; ++i) scanf("%lf", &q[i]), q[i] /= 100;
    dfs1(1, 0); dfs2(1, 0);
    double ans = 0;
    for(int i = 1; i <= n; ++i) ans += 1 - f[i] * g[i];
    printf("%.6lf
", ans);    
    return 0;
}