洛谷 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 概率與期望