[SHOI2014]概率充电器

发布于 2018-09-18  496 次阅读


题目大意:

给你一棵n个节点的树,每个点有$q_i$的概率被点亮,相邻的点有$p_i$的概率传递电流。
问点亮点数的期望。
对于 100%的数据,n≤500000,0≤p,qi≤100。

题要求被点亮点的期望个数
根据期望公式$ans=\sum_{i=1}^n(p_i \times x_i)$
这道题的$x_i=1$
所以就是求每个点被点亮的概率之和。
一个问题上数了,不是dp就是数据结构,或什么最短路魔改,点分治之类的。
这题显然让你树上期望dp
考虑什么情况某个点会被点亮。
我们不妨把这个无根树以1为根。
那么一个点的电可能来自他的父亲,他的儿子,他自己。
显然我们不能同时dp一个点的父亲和儿子。
我们可以开两个dp数组f和g

f[x]表示x被所在子树包括x充电的概率(被儿子充电或自己被充电)
g[x]表示x被他父亲充电的概率
w(x,y)表示x,y导电概率
那么
$f(x)=1-(1-q_x)*\prod\limits_{y∈son(x)}(1-f(y)) \times w(x,y)$
$g(x)=\biggl( 1-\frac{1-f(fa)}{1-f(x)\times w(x,fa)}\times \bigr(1-g(fa)\bigr) \biggr)\times w(x,fa)$
$ans=1-\biggl( 1-f(x)\biggr)\times \biggl( 1-g(x) \biggr)$
最后注意不要使分母是0就行。

#include <cstdio>
#include <algorithm>

using namespace std;
const int N=500005;

struct data
{
    int v,nxt;double val;
}edge[N<<1];
int cnt,alist[N];
inline void add(int u,int v,double val){edge[++cnt]=(data){v,alist[u],val},alist[u]=cnt;}
int n;
double p[N],f[N],g[N],ans;
bool vis[N];
inline void fuck(int x)
{
    f[x]=1-p[x];vis[x]=true;
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(vis[v]) continue;
        fuck(v);
        f[x]*=(1-f[v]*edge[i].val);
    }
    f[x]=1-f[x];vis[x]=false;
}
inline void you(int x)
{
    vis[x]=true;
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;double val=edge[i].val;
        if(vis[v]) continue;
        g[v]=1-f[v]*val<1e-9?0:(1-(1-f[x])/(1-f[v]*val)*(1-g[x]))*val;
        you(v);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;++i)
    {
        double z;
        scanf("%d%d%lf",&x,&y,&z);z/=100;
        add(x,y,z);add(y,x,z);  
    }
    for(int i=1;i<=n;++i) scanf("%lf",&p[i]),p[i]/=100;
    fuck(1);you(1);
    for(int i=1;i<=n;++i) ans+=1-(1-f[i])*(1-g[i]);
    printf("%.6lf",ans);

} 
5.00 avg. rating (96% score) - 1 vote

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。