【BZOJ】3566: [SHOI2014]概率充电器

【算法】树型DP+期望DP

【题意】一棵树上每个点均有直接充电概率q_i%，每条边有导电概率p_i%，问期望有多少结点处于充电状态？

【题解】引用自：【BZOJ3566】【SHOI2014】概率充电器树形DP 概率DP by 空灰冰魂

最大的难点在于计算每个点充电期望时，两个节点各自的期望都会影响对方的期望。

所以考虑转化对象，改为求每个节点充不上电的期望，充不上电就不用考虑两者的相互影响。

fi表示结点i由子结点和自身充不上电的概率

gi表示结点i由父结点充不上电的概率

第一次DFS：

hi表示结点i对父亲贡献的概率

fi=(1-qi)*∏_h[son[i]]

hi=fi+(1-fi)*(1-pi)　　pi为i到父亲的导线通电概率

☆两者发生其一用概率加法，多者都必须发生用概率乘法，P(A+B)=P(A)+P(B)-P(AB)注意去除交集。

第二次DFS：

当前结点x，父亲结点y。

t表示父亲y对结点x的贡献。

t=g_y*(f_y/h_x)　　注意h_x为0的情况（除0）

gx=t+(1-t)*(1-pi)　　pi为x到y的导线概率

最终答案：ans=Σ(1-fi*gi)　　因为概率和期望都是0~1，所以一样。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

struct edge{int v,from;double p;}e[maxn*];

int n,first[maxn],tot;

double q[maxn],f[maxn],g[maxn],h[maxn],fw[maxn];

void insert(int u,int v,double w)

{tot++;e[tot].v=v;e[tot].p=w;e[tot].from=first[u];first[u]=tot;}

void dfs1(int x,int fa)

{

    f[x]=-q[x];

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)

    {

        dfs1(e[i].v,x);

        f[x]*=h[e[i].v];

    }else fw[x]=e[i].p;

    h[x]=f[x]+(-f[x])*(-fw[x]);

}

void dfs2(int x,int y)

{

    double t;

    if(!h[x])t=;else t=g[y]*f[y]/h[x];

    g[x]=t+(-t)*(-fw[x]);

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=y)dfs2(e[i].v,x);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++)

    {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        insert(u,v,1.0*w/);

        insert(v,u,1.0*w/);

    }

    for(int i=;i<=n;i++){int u;scanf("%d",&u);q[i]=1.0*u/;}

    dfs1(,);

    dfs2(,);

    double ans=;

    for(int i=;i<=n;i++)ans+=-f[i]*g[i];

    printf("%.6lf",ans);

    return ;

}

巴特西

【BZOJ】3566: [SHOI2014]概率充电器

最新文章

热门文章