BZOJ 3566 概率充电器 解题报告

3566: [SHOI2014]概率充电器

Time Limit: 40 Sec  Memory Limit: 256 MB

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。

Solution

显然，题目中描述了一颗无根树，为了方便，我们令1号节点为根。
       一个元件或者说一个节点可以被充电的充分条件有：该节点主动进入充电状态、该节点的父节点将电力传递过来、该节点的子节点中的至少一个将电力传递过来，我们将它们简记为S、U、D，概率用P表示。对于P(S)可以直接计算，对于P(U)和P(D)，计算起来比较复杂。
       设posi[i]为i节点主动进入充电状态的概率（记为P(i.S)），dp1[i]为i节点无法从下方获得电力进入充电状态的概率（即1-P(i.D)）,dp2[i]表示1-P(i.U)。一个点进入充电状态的概率P(i)=1-(1-P(i.S))×(1-P(i.D))×(1-P(i.U))=1-(1-posi[i])*dp1[i]*dp2[i]。
       然后我们看一看dp1、dp2的求法，如图：
容易看出，$dp1_i=\Π[1-(1-dp1_j×weight(i,j)],where\ j∈i.child$
这意味着，dp1的值是向上传递的，可以用DFS的逆序跟新。
       dp2的更新复杂得多。dp2[i]的直接来源只有P(i.parent)，但这个直接来源无法直接使用，因为P(i.parent)的值的计算需要使用dp2[i.parent]和dp1[i.parent]，其中包含i的贡献，直接使用无疑会造成重复计算。我们考虑dp2[i]的间接来源，包括dp2[i.parent]和dp1[i.brother]，也就是i.parent的父节点和i.parent除了i之外的子节点。由于乘法运算具有可逆性，我们可以考虑用dp1[i.parent]÷(1-(1-dp1[i])×weight(i.parent,i))，也就是用i.parent的子节点对dp1[i.parent]的总贡献除以其中i的贡献。即$$dp2_i=1-[1-dp2_{i.parent}×{dp1_{i.parent}}/{1-(1-dp1_i)×weight(i,i.parent)}]×weight(i,i.parent)$$公式很长，但理解起来不困难。与dp1相反dp2的值向下传递，可以按DFS序更新。
       到目前为止，本题和普通的树形DP的方法基本一致。
       考虑这样的情况：dp1[i]=0，weight[i,i.parent]=1，于是就发生了除零错误。为了避免除零错误，我们可以考虑用10-8代替0，但用极小的数作为除数会产生极大的精度损失。我们分情况讨论，若i.parent的子节点中只有一个0，则这个是零的子节点的值等于其他子节点贡献度，其他节点的dp2等于1-weight(i,i.parent)；若i.parent的子节点中有超过一个零，则i.parent的所有子节点的dp2均等于1-weight(i,i.parent)；若i.parent的子节点中没有零，则所有子节点正常更新。实现如下：
void dfs2(int now)
{
    //小心除零错误！
    int cntzero = 0;
    long double other = 1;
    int pzero;
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (parent[now] != graph[i].front)
        {
            if (tmpdp1[graph[i].front]<1e-10)
            {
                cntzero++;
                pzero = graph[i].front;
                if (cntzero>1)break;
            }
            else
            {
                other *= tmpdp1[graph[i].front];
            }
        }
    }
    //情况一：parent[i]的子节点中至少有两个贡献度为零
    //——无论向谁转移，parent一定会充电
    if (cntzero>1)
    {
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front)
            {
                dp2[graph[i].front] = (long double)1 - graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
    //情况二
    //——正常转移，无除零错误
    else if (cntzero == 0)
    {
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front)
            {
                dp2[graph[i].front] = (long double)1 - ((long double)1 - dp2[now] * dp1[now] / tmpdp1[graph[i].front] * ((long double)1 - posi[now]))*graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
    //情况三
    //——pzero正常转移，其他同情况一
    else
    {
        dp2[pzero] = (long double)1 - ((long double)1 - dp2[now] * other*((long double)1 - posi[now]))*distop[pzero];
        dfs2(pzero);
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front&&graph[i].front != pzero)
            {
                dp2[graph[i].front] = (long double)1 - graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
}

Code

//概率分为三部分：自己、下方、上方
#include <iostream>
#include <stdio.h>
using namespace std;

inline void read(int &x)
{
    x = 0; char ch = getchar(); bool f = 0;
    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    if (f)x = -x;
}

inline void read(long long &x)
{
    x = 0; char ch = getchar(); bool f = 0;
    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    if (f)x = -x;
}

struct graph_t
{
    int front, nex;
    long double weight;
}graph[1500001];
int tail = 500000;

void addedge(int u, int v, long double w)
{
    int tmp1 = graph[u].nex, tmp2 = graph[v].nex;
    graph[u].nex = ++tail, graph[v].nex = ++tail;
    graph[tail - 1].front = v, graph[tail].front = u;
    graph[tail - 1].weight = w, graph[tail].weight = w;
    graph[tail - 1].nex = tmp1, graph[tail].nex = tmp2;
}

//dp1:下->上 dp2:上->下
long double dp1[500001];//不可能的概率
long double tmpdp1[500001];//dp1跟新时，每个节点对父节点的贡献度
long double dp2[500001];
long double posi[500001];
int parent[500001];
long double distop[500001];
bool vis[500001];

void dfs1(int now)
{
    dp1[now] = 1;
    vis[now] = true;
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (!vis[graph[i].front])
        {
            parent[graph[i].front] = now;
            distop[graph[i].front] = graph[i].weight;
            dfs1(graph[i].front);
            tmpdp1[graph[i].front] = ((long double)1 - ((long double)1 - dp1[graph[i].front]
                * ((long double)1 - posi[graph[i].front]))*graph[i].weight);
            dp1[now] *= tmpdp1[graph[i].front];
        }
    }
}

void dfs2(int now)
{
    //小心除零错误！
    int cntzero = 0;
    long double other = 1;
    int pzero;
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (parent[now] != graph[i].front)
        {
            if (tmpdp1[graph[i].front]<1e-10)
            {
                cntzero++;
                pzero = graph[i].front;
                if (cntzero>1)break;
            }
            else
            {
                other *= tmpdp1[graph[i].front];
            }
        }
    }
    //情况一：parent[i]的子节点中至少有两个贡献度为零
    //——无论向谁转移，parent一定会充电
    if (cntzero>1)
    {
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front)
            {
                dp2[graph[i].front] = (long double)1 - graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
    //情况二
    //——正常转移，无除零错误
    else if (cntzero == 0)
    {
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front)
            {
                dp2[graph[i].front] = (long double)1 - ((long double)1 - dp2[now] * dp1[now] / tmpdp1[graph[i].front] * ((long double)1 - posi[now]))*graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
    //情况三
    //——pzero正常转移，其他同情况一
    else
    {
        dp2[pzero] = (long double)1 - ((long double)1 - dp2[now] * other*((long double)1 - posi[now]))*distop[pzero];
        dfs2(pzero);
        for (int i = graph[now].nex; i; i = graph[i].nex)
        {
            if (parent[now] != graph[i].front&&graph[i].front != pzero)
            {
                dp2[graph[i].front] = (long double)1 - graph[i].weight;
                dfs2(graph[i].front);
            }
        }
    }
}

int main()
{
    int v;
    read(v);
    for (int i = 1; i<v; i++)
    {
        int from, to, p;
        read(from); read(to); read(p);
        addedge(from, to, (long double)(p) / 100.0);
    }
    for (int i = 1; i <= v; i++)
    {
        int tmp;
        read(tmp);
        posi[i] = (long double)(tmp) / 100.0;
    }
    dfs1(1);
    dp2[1] = 1;
    dfs2(1);
    long double ans = 0;
    for (int i = 1; i <= v; i++)
    {
        ans += (long double)1 - ((long double)1 - posi[i])*dp1[i] * dp2[i];
    }
    printf("%.6Lf", ans);
    return 0;
}

时间：
标签： ,

没有评论:

发表评论

订阅： 博文评论 (Atom)