[SHOI2014]概率充电器

Description:

给定一棵\(n\)个点的树,每个点有\(p_i\)的概率被直接充电,同时每条边有\(w_i\)的概率联通两个点,使它们互相通电,问通电数目的期望个数

Hint:

\(n \le 5*10^5\)

Solution:

首先我们考虑一个点连上它子树的不通电概率(这里转化为"不"是为了方便算,不转化也能做)

有:

\(f[u]=\prod_i( f[v_i]+(1-f[v_i])*(1-w_i))\)

注意到v不通电和v通电但边不通电是互斥事件,故我们可以把概率直接加起来

对于子树以外的部分,直接换根\(dp?\)就行,详见代码:

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=5e5+5;
int n,cnt,hd[mxn];
double ans,f[mxn],p[mxn],dp[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline int chkmax(int &x,int y) {if(x<y) x=y;}
inline int chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt;
    double w;
}t[mxn<<1];

inline void add(int u,int v,double w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

void dfs1(int u,int fa) 
{
    f[u]=1-p[u];
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        dfs1(v,u);
        f[u]*=(f[v]+(1.0-f[v])*t[i].w);
    }
}

void dfs2(int u,int fa) 
{
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        double tp=dp[u]/(f[v]+(1.0-f[v])*t[i].w);
        dp[v]=f[v]*(tp+(1.0-tp)*t[i].w);
        dfs2(v,u);
    }
}

int main()
{
    n=read(); int u,v; double w; 
    for(int i=1;i<n;++i) {
        u=read(); v=read(); w=read(); w=100.0-w;
        add(u,v,w/100.0); add(v,u,w/100.0);
    }
    for(int i=1;i<=n;++i) p[i]=read()/100.0;
    dfs1(1,0); dp[1]=f[1]; dfs2(1,0);
    for(int i=1;i<=n;++i) ans+=1.0-dp[i]; //最后答案直接累加即可
    printf("%.6lf",ans);
    return 0;
}

[SHOI2014]概率充电器

原文：https://www.cnblogs.com/list1/p/10527033.html