【题解】Luogu P4284 [SHOI2014]概率充电器

原题传送门

我们知道，每个电器充电对充电电器数的贡献都是相等的1，所以若第$i$个电器有$p_i$的概率充电时

$$E=\sum_{i=1}^np_i$$

我们考虑如何求$p_i$，根据树形dp的套路，肯定是自己子树的贡献和非自己子树贡献的结合

设$f_i$表示自己及自己的子树不能给自己充电的概率，$g_i$表示非子树节点和自己不能给自己充电的概率，易知

$$p_i=1-f_ig_i$$

我们考虑如何求$f_i$,$g_i$

对于$f_i$:

$$f_i=(1-direct_i)\prod_{v \in son_i}(f_v+(1-f_v)(1-edge[i->v].p))$$

解释一下：首先要自己不直接通电，然后任意一个儿子要么不通电，要么通电且与自己的电线不通

对于$g_i$

设$$tmp=\frac{g_{fa}f_{fa}}{f_i+(1-f_i)(1-edge[fa->i].p)}$$

则$$g_i=tmp+(1-tmp)*(1-edge[fa->i].p)$$

$tmp$表示除了自己和自己的子树通电，自己父亲通电的概率。那么从非子树和自己来的电就是父亲不通电的概率与父亲通电但自己与父亲电线不通的概率之和

注意：题目给的是百分数，要处以$100.0$；我们拟定$1$为根节点，所以初始条件为$g_1=1$

#include <bits/stdc++.h>

#define db double

#define N 500005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

struct edge{

	int to,next;

	db w;

}e[N<<1];

int head[N],cnt=0;

inline void add(register int u,register int v,register db w)

{

	++cnt;

	e[cnt].to=v,e[cnt].next=head[u],e[cnt].w=w;

	head[u]=cnt;

}

int n;

db a[N],g[N],f[N],ans;

inline void dfs1(register int x,register int fa)

{

	f[x]=1.0-a[x];

	for(register int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa)

			continue;

		dfs1(v,x);

		f[x]*=f[v]+(1.0-f[v])*(1.0-e[i].w);

	}

}

inline void dfs2(register int x,register int fa)

{

	for(register int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa)

			continue;

		double tmp=g[x]*f[x]/(f[v]+(1.0-f[v])*(1.0-e[i].w));

		g[v]=tmp+(1.0-tmp)*(1.0-e[i].w);

		dfs2(v,x);

	}

}

int main()

{

	n=read();

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

	{

		int u=read(),v=read(),w=read();

		add(u,v,w/100.0),add(v,u,w/100.0);

	}

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

	{

		int x=read();

		a[i]=x/100.0;

	}

	dfs1(1,0);

	g[1]=1.0;

	dfs2(1,0);

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

		ans+=(1.0-g[i]*f[i]);

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

    return 0;

}

巴特西

【题解】Luogu P4284 [SHOI2014]概率充电器

原题传送门

我们知道，每个电器充电对充电电器数的贡献都是相等的1，所以若第\(i\)个电器有\(p_i\)的概率充电时

$$E=\sum_{i=1}^np_i$$

我们考虑如何求\(p_i\)，根据树形dp的套路，肯定是自己子树的贡献和非自己子树贡献的结合

设\(f_i\)表示自己及自己的子树不能给自己充电的概率，\(g_i\)表示非子树节点和自己不能给自己充电的概率，易知

$$p_i=1-f_ig_i$$

我们考虑如何求\(f_i\),\(g_i\)

对于\(f_i\):

$$f_i=(1-direct_i)\prod_{v \in son_i}(f_v+(1-f_v)(1-edge[i->v].p))$$

解释一下：首先要自己不直接通电，然后任意一个儿子要么不通电，要么通电且与自己的电线不通

对于\(g_i\)

设$$tmp=\frac{g_{fa}f_{fa}}{f_i+(1-f_i)(1-edge[fa->i].p)}$$

则$$g_i=tmp+(1-tmp)*(1-edge[fa->i].p)$$

\(tmp\)表示除了自己和自己的子树通电，自己父亲通电的概率。那么从非子树和自己来的电就是父亲不通电的概率与父亲通电但自己与父亲电线不通的概率之和

注意：题目给的是百分数，要处以\(100.0\)；我们拟定\(1\)为根节点，所以初始条件为\(g_1=1\)

最新文章

热门文章