NC20589. [SHOI2014]概率充电器
描述
输入描述
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的 充电元件,通电概率为 p%。第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。
输出描述
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
示例1
输入:
3 1 2 50 1 3 50 50 0 0
输出:
1.000000
C++11(clang++ 3.9) 解法, 执行用时: 658ms, 内存消耗: 65216K, 提交时间: 2020-03-27 18:23:01
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
vector<pair<int,int> >G[N];
double dp[N],p[N];
int n;
void dfs1(int x,int fa)
{
dp[x]=1-p[x];//表示当前节点不来电的概率
for(auto S:G[x])
{
int v=S.first,w=S.second;
if(v==fa) continue;
dfs1(v,x);
dp[x]*=1-(1-dp[v])*(1.0*w/100);
}
}
void dfs2(int x,int fa)//换根
{
for(auto S:G[x])
{
int v=S.first,w=S.second;
if(v==fa) continue;
double tmp=1-(1-dp[v])*(1.0*w/100);
if(tmp>1e-8) dp[v]=dp[v]*(1-(1-dp[x]/tmp)*(1.0*w/100));
dfs2(v,x);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++)
{
int x,y,w;
cin>>x>>y>>w;
G[x].push_back(make_pair(y,w));
G[y].push_back(make_pair(x,w));
}
for(int i=1;i<=n;i++) cin>>p[i],p[i]=1.0*p[i]/100;
dfs1(1,0);
dfs2(1,0);
double ans=0;
for(int i=1;i<=n;i++) ans+=(1-dp[i]);
printf("%.6f\n",ans);
return 0;
}