关键词：
题目描述
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
输入
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。
输出
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
样例输入
3
1 2 50
1 3 50
50 0 0
样例输出
1.000000
题解
树形概率dp
先自下至上dp，求出每个子树中根节点不能工作的概率$f[x]$。其中工作需要子节点字数能工作且边存在。
然后自上至下dp，更新每个点能工作的概率$g[x]$，计算出父树的贡献，方法同理。
具体的dp方程：
$f[x]=(1-w[x])*prod(1-f[to[i]]*val[i])$
$g[1]=f[1]$
$g[to[i]]=f[to[i]]*(1-(1-frac{g[x]}{1-(1-f[to[i]])*val[i]})*val[i])$。
注意可能产生的除0的情况，此时$g[x]$必然等于0，特判一下就好了。
最后的答案即为$sumlimits_{i=1}^ng[i]$。
#include <cstdio>
#define N 500010
const double eps = 1e-7;
int head[N] , to[N << 1] , next[N << 1] , cnt;
double val[N << 1] , w[N] , f[N] , g[N];
void add(int x , int y , double z)
{
to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;
}
void dfs1(int x , int fa)
{
int i;
f[x] = 1 - w[x];
for(i = head[x] ; i ; i = next[i])
if(to[i] != fa)
dfs1(to[i] , x) , f[x] *= 1 - (1 - f[to[i]]) * val[i];
}
void dfs2(int x , int fa)
{
int i;
for(i = head[x] ; i ; i = next[i])
{
if(to[i] != fa)
{
if(1 - (1 - f[to[i]]) * val[i] < eps) g[to[i]] = f[to[i]] * val[i];
else g[to[i]] = f[to[i]] * (1 - (1 - g[x] / (1 - (1 - f[to[i]]) * val[i])) * val[i]);
dfs2(to[i] , x);
}
}
}
int main()
{
int n , i , x , y;
double z , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i < n ; i ++ ) scanf("%d%d%lf" , &x , &y , &z) , add(x , y , z / 100) , add(y , x , z / 100);
for(i = 1 ; i <= n ; i ++ ) scanf("%lf" , &w[i]) , w[i] /= 100;
dfs1(1 , 0) , g[1] = f[1] , dfs2(1 , 0);
for(i = 1 ; i <= n ; i ++ ) ans += 1 - g[i];
printf("%.6lf
" , ans);
return 0;
}
●bzoj3566[shoi2014]概率充电器
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3566题解：概率dp，树形dp 如果求出每个点被通电的概率t， 那么期望答案就是t1×1+t2×1+t3*1+...+tn×1 现在问题就是要去求每个点被通电的概率。 因为是一颗树，所以每个点是否... 查看详情
bzoj3566:[shoi2014]概率充电器树形概率dp(代码片段)
设g[u]为这个点被儿子和自己充上电的概率，f[u]为被儿子、父亲和自己充上电的概率然后根据贝叶斯公式（好像是叫这个），1.P(A+B)=P(A)+P(B)-P(A)*P(B)，2.P(A)=(P(A+B)-P(B))/(1-P(B))g的转移很好想，根据上面的1公式，g[u]=g[u]+g[e[i].to]*e[i].p-g... 查看详情
bzoj3566:[shoi2014]概率充电器
...SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-... 查看详情
bzoj3566[shoi2014]概率充电器
...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数 查看详情
bzoj3566
3566:[SHOI2014]概率充电器TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 982 Solved: 422[Submit][Status][Discuss]Description著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全 查看详情
bzoj3566概率充电器（动态规划）
【BZOJ3566】概率充电器（动态规划）题面BZOJDescription著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您... 查看详情
[bzoj3566][shoi2014]概率充电器(代码片段)
传送门DescriptionSHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元... 查看详情
bzoj3566概率充电器概率dp
哼我就要正着推链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3566 题意：节点有没有电看脸，线好不好看脸，问一个正常的亚洲人会给几个东西充上电。我就正着推了怎么地首先，我们定义一下数组含义，$f[x]$表示这个点有电... 查看详情
[shoi2014]概率充电器
[SHOI2014]概率充电器题目著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必... 查看详情
[shoi2014]概率充电器
...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充... 查看详情
loj#2192.「shoi2014」概率充电器(代码片段)
Loj#2192.「SHOI2014」概率充电器题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：「采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI概率充电器，您生活不... 查看详情
p4284[shoi2014]概率充电器(代码片段)
P4284[SHOI2014]概率充电器链接：https://www.luogu.org/problemnew/show/P4284题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随... 查看详情
[shoi2014]概率充电器(代码片段)
...生都能看懂（大佬就是大佬啊）：题解P4284【[SHOI2014]概率充电器】，第二次dp的状态方程真的很妙啊。刚开始我总按照套路想设\(dp[u]\)表示\(u\)的子树的期望，看完题解后发现这是没有依据的，因为每一个元件可以直接充电，不... 查看详情
shoi2014概率充电器(代码片段)
题目链接：戳我非常不好意思，因为想要排版，所以今天先只把代码贴出来，明天补题解。QAQ#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#defineeps1e-7#defineMAXN500010intn,m,t;in 查看详情
解题：shoi2014概率充电器(代码片段)
题面显然就是在求概率，因为期望乘的全是1.。。。然后就推推推啊设$fgg[i]$表示这个点父亲没给他充上电的概率，$sgg[i]$表示这个点子树(和它自己没给他充上电的概率)，然后这个点没充上电的概率就是$fgg[i]*sgg[i]$我们发现我们... 查看详情
[题解]luogup4284[shoi2014]概率充电器(代码片段)
https://www.luogu.com.cn/problem/P4284比较套路的概率题？由期望的线性性可以把每个点拆开来，然后答案就是每个点通电的概率之和。通电的概率并不怎么好算，我们可以算点(u)不通电的概率(f[u])，然后答案就是[sumlimits_i=1^n1-f[i]]发现... 查看详情
bzoj4871:[shoi2017]摧毁“树状图”树形dp(代码片段)
做不来……参考https://www.cnblogs.com/ezyzy/p/6784872.html#include<iostream>#include<cstdio>usingnamespacestd;constintN=100005;intT,o,n,h[N],cnt,f[N],g[N],q[N],q1[N],l[N],l1[N];structqweintne,to 查看详情
bzoj3564[shoi2014]信号增幅仪
3564:[SHOI2014]信号增幅仪TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 738 Solved: 290[Submit][Status][Discuss]Description无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比 查看详情