BZOJ3566 概率充电器树形概率dp

不念不忘少年蓝@ 2022-05-15 08:00 201阅读 0赞

[传送门][Link 1]

题意：给你一棵树，求能充电节点的期望个数，每条边都有一个概率，每个点也有一个概率。

思路：

从反面考虑：

设s\[u\]是u没电，以及它的孩子也不会给他充电。

![s\[u\]=(1-p\[u\])\*\\prod\_\{v->son\}(1-pt+pt\*s\[v\])][s_u_1-p_u_prod_v-_son_1-pt_pt_s_v] （pt是边的概率）

f\[u\]是父亲不给供电

从父亲的电有两个来源，一个是自己兄弟，另一个是父亲的父亲。

我们先在上面求出h\[v\]=1-pt+pt\*s\[v\]

![f\[v\]=pt\*f\[u\]\*s\[u\]/h\[v\]+1-pt][f_v_pt_f_u_s_u_h_v_1-pt]

所以期望就是E=E+1-s\[i\]\*f\[i\];

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e5+10;
    const double eps=1e-10;
    struct edge{
        int to, nxt;
        double p;
    }edg[N<<1];
    double p[N], f[N], s[N], h[N];//s[i]不能被自己和孩子供电, f[i]不能被父亲供电
    int n, head[N], cnt;
    
    void addedg(int u, int v, double pi){
        edg[cnt].to=v; edg[cnt].p=pi; edg[cnt].nxt=head[u];
        head[u]=cnt++;
    }
    
    int getint()
    {
        int i=0,f=1;char c;
        for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
        if(c=='-')f=-1,c=getchar();
        for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
        return i*f;
    }
    
    void dfs(int u, int fa){
        s[u]=1-p[u];
    
        for(int i=head[u]; ~i; i=edg[i].nxt){
            int v=edg[i].to;
            double pt=edg[i].p;
            if(v==fa) continue;
            dfs(v, u);
            h[v]=(pt*s[v]+1-pt);
            s[u]*=h[v];
        }
    
    }
    
    void dfs2(int u, int fa){
        for(int i=head[u]; ~i; i=edg[i].nxt){
            int v=edg[i].to;
            double pt=edg[i].p;
            if(v==fa) continue;
            double t=h[v]<eps?0:f[u]*s[u]/h[v];
            f[v]=pt*t+1-pt;
            dfs2(v, u);
        }
    }
    
    int main(){
        memset(head, -1, sizeof head);
        n=getint();
        int u, v, pi;
    
        for(int i=1; i<n; i++){
            u=getint(); v=getint(); pi=getint();
            addedg(u, v, 1.0*pi/100);
            addedg(v, u, 1.0*pi/100);
        }
    
        for(int i=1; i<=n; i++)
            pi=getint(), p[i]=1.0*pi/100;
        dfs(1, -1);
        f[1]=1;
        dfs2(1, -1);
        double ans=0;
    
        for(int i=1; i<=n; i++){
            ans+=1-f[i]*s[i];
        }
        printf("%.6f\n", ans);
        return 0;
    }

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3566
[s_u_1-p_u_prod_v-_son_1-pt_pt_s_v]: https://private.codecogs.com/gif.latex?s%5Bu%5D%3D%281-p%5Bu%5D%29*%5Cprod_%7Bv-%3Eson%7D%281-pt&plus;pt*s%5Bv%5D%29
[f_v_pt_f_u_s_u_h_v_1-pt]: https://private.codecogs.com/gif.latex?f%5Bv%5D%3Dpt*f%5Bu%5D*s%5Bu%5D/h%5Bv%5D&plus;1-pt