P4284-[SHOI2014]概率充电器
题目:
题目描述:
著名的电子产品品牌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%。
输出格式:
输出一行一个实数，为能进入充电状态的元件个数的期望，四舍五入到小
数点后6 位小数。
样例:
样例输入1:
1
2
3
4
| 3
1 2 50
1 3 50
50 0 0
|
样例输出1:
样例输入2:
1
2
3
4
5
6
| 5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40
|
样例输出2:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include "ybwhead/ios.h"
int n;
const int maxn = 500050;
int head[maxn], tot;
struct edge
{
int v, nxt;
double w;
} e[maxn << 1];
void __ADD(int u, int v, double w)
{
e[++tot] = {v, head[u], w};
head[u] = tot;
}
void add(int u, int v, double w)
{
__ADD(u, v, w);
__ADD(v, u, w);
}
double x[maxn];
double f[maxn];
double g[maxn];
void dfs1(int u, int fa)
{
f[u] = 1 - x[u];
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
dfs1(v, u);
f[u] *= (1 - e[i].w + e[i].w * f[v]);
}
}
void dfs2(int u, int fa)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
double tmp = g[u] / (1 - e[i].w + e[i].w * f[v]);
g[v] = f[v] * (1 - e[i].w + e[i].w * tmp);
dfs2(v, u);
}
}
int main()
{
yin >> n;
for (int i = 1; i < n; i++)
{
int x, y;
double z;
yin >> x >> y >> z;
add(x, y, z / 100);
}
for (int i = 1; i <= n; i++)
{
yin >> x[i];
x[i] /= 100;
}
dfs1(1, 0);
g[1] = f[1];
dfs2(1, 0);
double ans = 0;
for (int i = 1; i <= n; i++)
ans += 1 - g[i];
yout << ans << endl;
return 0;
}
|