洛谷 P4284 [SHOI2014]概率充电器概率与期望+换根DP

2020 年 8 月 27 日
筆記
DP--树形DP, 概率与期望

洛谷 P4284 [SHOI2014]概率充电器概率与期望+换根DP

题目描述

著名的电子产品品牌\(SHOI\) 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器：

“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！\(SHOI\) 概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”

\(SHOI\) 概率充电器由\(n-1\) 条导线连通了\(n\) 个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为\(SHOI\) 公司的忠实客户，你无法抑制自己购买\(SHOI\) 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的\(SHOI\) 概率充电器。你迫不及待地将\(SHOI\) 概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

输入格式

第一行一个整数：\(n\)。概率充电器的充电元件个数。充电元件由\(1-n\) 编号。

之后的\(n-1\) 行每行三个整数\(a, b, p\)，描述了一根导线连接了编号为\(a\) 和\(b\) 的充电元件，通电概率为\(p\%\)。

第\(n+2\) 行\(n\) 个整数：\(q_i\)。表示\(i\) 号元件直接充电的概率为\(q_i\%\)。

输出格式

输出一行一个实数，为能进入充电状态的元件个数的期望，四舍五入到小数点后\(6\) 位小数。

输入输出样例

输入 #1复制

输出 #1复制

1.000000

输入 #2复制

5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40

输出 #2复制

4.300000

说明/提示

对于\(30\%\)的数据，\(n≤5000\)。

对于\(100\%\)的数据，\(n≤500000,0≤p,q_i≤100\)。

分析

对于一个元件，它可以被与它相邻的多个元件所影响

如果我们想要一次求出所有的结果，\(DP\)的顺序是不好规定的

因此我们可以先随便选一个点作为根节点，求出每一个点自己点亮自己和被子树点亮的概率

这样选定的根节点求出的结果是正确的

我们就可以继续使用换根\(DP\)求出其他的值

如果求被点亮的概率转移比较麻烦，因此我们设\(f[i]\)为\(i\)不被点亮的概率

那么\(f[i]=(1.0-val[i,j]+val[i,j] \times f[j])\)，\(j\)是\(i\)的儿子节点

如果\(i\)和\(j\)之间的边都没有通电，那么\(i\)被\(j\)点亮肯定是不可以的

即使边通了电，也要保证\(j\)通电才可以

换根的时候，我们定义\(g[i]\)为节点\(i\)通电的概率

对于之前的根节点，直接继承即可

对于其它任意一个节点\(i\)，如果我们要更新儿子节点\(j\)的话

我们首先把\(j\)所在子树的价值从\(i\)中刨去

再用得到的值去更新\(g[j]\)即可

代码

#include<cstdio>
#include<cstring>
const int maxn=1e6+5;
int head[maxn],tot=1,n;
struct asd{
    int to,next;
    double val;
}b[maxn];
void ad(int aa,int bb,int cc){
    b[tot].to=bb;
    b[tot].next=head[aa];
    b[tot].val=(double)cc*0.01;
    head[aa]=tot++;
}
double f[maxn],p[maxn],g[maxn];
void dfs(int now,int fa){
    f[now]=p[now];
    for(int i=head[now];i!=-1;i=b[i].next){
        int u=b[i].to;
        if(u==fa) continue;
        dfs(u,now);
        f[now]*=(1.0-b[i].val+b[i].val*f[u]);
    }
}
void dfs2(int now,int fa,double lat){
    if(now==1){
        g[now]=f[now];
    } else {
        double P=g[fa]/(1.0-lat+lat*f[now]);
        g[now]=f[now]*(1.0-lat+lat*P);
    }
    for(int i=head[now];i!=-1;i=b[i].next){
        int u=b[i].to;
        if(u==fa) continue;
        dfs2(u,now,b[i].val);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int aa,bb,cc;
        scanf("%d%d%d",&aa,&bb,&cc);
        ad(aa,bb,cc);
        ad(bb,aa,cc);
    }
    for(int i=1;i<=n;i++){
        int aa;
        scanf("%d",&aa);
        p[i]=1.0-(double)aa*0.01;
    }
    dfs(1,0);
    dfs2(1,0,0);
    double ans=0;
    for(int i=1;i<=n;i++){
        ans+=(1.0-g[i]);
    }
    printf("%.6f\n",ans);
    return 0;
}

Tags: DP--树形DP 概率与期望