[BZOJ3566/Luogu4284][SHOI2014]概率充电器(动态规划)

发布于 2018-04-04  69 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3566/Luogu4284][SHOI2014]概率充电器(动态规划)

Description

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

Tag

动态规划

解决思路

经典的树上换根动态规划。
把通电的点的数量期望转化为每一个点通电的概率适合。由于直接考虑通电的情况,需要考虑很多状态,不妨转化为不通电的概率。
那么先求子树的贡献,要么它自己直接没电,否则自己有电的时候,要么连接到儿子的边没有电;若连到儿子的边通电则要求儿子不通电。分别讨论三种情况转移过来。
然后再把父亲的通电情况转移过来,首先去掉自己的贡献,然后还是分边不导电和边导电点不导电来转移。这样得到不导电的概率,用1减去就是导电的概率了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=501000;
const int maxM=maxN*2;
const int inf=2147483647;

int n;
ld Node[maxN];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ld W[maxM];
ld F[maxN];

void Add_Edge(int u,int v,int w);
void dfs1(int u,int fa);
void dfs2(int u,int fa,ld gl);

int main()
{
    ios::sync_with_stdio(false);mem(Head,-1);

    cin>>n;
    for (int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        Add_Edge(u,v,w);Add_Edge(v,u,w);
    }
    for (int i=1;i<=n;i++)
    {
        int w;cin>>w;
        Node[i]=(ld)w/(ld)(100);
    }
    dfs1(1,1);//子树内的
    dfs2(1,1,1);//把父亲的导下来
    ld Ans=0;
    for (int i=1;i<=n;i++) Ans=Ans+(1-F[i]);
    printf("%.6LF\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    ld ww=(ld)w/(ld)100;
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=ww;
    return;
}

void dfs1(int u,int fa)
{
    F[u]=1-Node[u];//自身不导电
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            dfs1(V[i],u);
            F[u]=F[u]*((1-W[i])+W[i]*F[V[i]]);//边不导电+边导电但点不导电
        }
    return;
}

void dfs2(int u,int fa,ld gl)
{
    F[u]=F[u]*gl;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            ld t=(1-W[i])+W[i]*F[V[i]];//t计算出这个点传递到父亲的答案
            t=F[u]/t;//得到父亲去掉这个点的答案
            dfs2(V[i],u,t+((ld)1-t)*((ld)1-W[i]));//还是分别讨论边不导电和边导电但点不导电两种情况
        }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3566/Luogu4284][SHOI2014]概率充电器(动态规划)


HNCJ OIer