首页 > 代码库 > bzoj 3566: [SHOI2014]概率充电器
bzoj 3566: [SHOI2014]概率充电器
Description
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!
”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
Input
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。
Output
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
Sample Input
1 2 50
1 3 50
50 0 0
Sample Output
HINT
对于 100%的数据,n≤500000,0≤p,qi≤100。
Source
By 佚名提供
题目要求充电元件个数的期望，由于期望的线性性，我们可以算每个元件充电的概率，然后累加。。。
考虑一个元件通电的概率不太好算，那么我们可以算一个元件不通电的概率。。。
首先对于这种无根树，按树形dp的套路，先变成有根树，第一遍考虑子树内，然后第二遍考虑子树外，两遍dp。。。
那么首先第一遍dp，假如y是x的儿子，因为不通电要所有都不通电，所以概率要相乘，那么我们需要知道x,y不连通的概率。。。
不连通的概率直接算貌似不好算，那我们可以算通电的概率，然后用1减去即可，通电的话需要元件和导线都导电，那么要把概率相乘。。。
dp[x]的初值为(1-q[x])，所以：
然后进行第二遍dp，考虑y与父亲x的转移，那么容易知道：
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1000050;
const double eps=1e-9;
double dp[N],p[N],q[N];
int head[N],nxt[N],to[N],fa[N],cnt,n;
void lnk(int x,int y,double g){
to[++cnt]=y,nxt[cnt]=head[x],p[cnt]=g,head[x]=cnt;
to[++cnt]=x;nxt[cnt]=head[y],p[cnt]=g,head[y]=cnt;
}
void dfs1(int x,int f){
dp[x]=(1-q[x]);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=f){
fa[y]=x;dfs1(y,x);
dp[x]*=(1-p[i]*(1-dp[y]));
}
}
}
void dfs2(int x){
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=fa[x]){
double gg=1-dp[x]/(1-p[i]*(1-dp[y]));
if(gg>eps) dp[y]*=(1-p[i]*gg);
dfs2(y);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b;double g;
scanf("%d%d",&a,&b);scanf("%lf",&g);g/=100;
lnk(a,b,g);
}
for(int i=1;i<=n;i++) scanf("%lf",&q[i]),q[i]/=100;
double ans=0;dfs1(1,1);dfs2(1);
for(int i=1;i<=n;i++) ans+=(1-dp[i]);
printf("%.6f\n",ans);
return 0;
}
bzoj 3566: [SHOI2014]概率充电器