题目链接
bzoj3566: [SHOI2014]概率充电器
题解
考虑一个点不连通的概率 计算概率的式子\(P(A)\)表示\(A\)发生的概率\(P(A+B)\)表示\(A,B\)至少发生一个的概率\(P(A+B)=P(A)+P(B)-P(AB)\) $P(A)=(P(A+B)-P(B))/(1-P(B)) $ 然后你直接用上式计算父亲对儿子，儿子对父亲的转移，就OK
考虑一个点不连通的概率 设f[x]表示x不通电的概率 考虑x的儿子对它的贡献，那么\(f[x] = (1 - p[x]) * \pi (1-(1-f[v]) * w)\) ,v为x的儿子，w为边连通的概率。 考虑v的父亲x对v的贡献，我们设k 为x除去v这个点连通的概率，那么\(P = 1 - \frac{f[x]}{(1 - (1 - f[v]) * w)} 。\) 于是$f[v] = 1 - P w $ 对于上式，两边dfs求出\(f[x]\)\(ans=\sum_{i = 1}^{n}1-f[i]\) 注意精度，判nan
代码
/*
考虑一个点不连通的概率
计算概率的式子
P(A)表示A发生的概率
P(A+B)表示A,B至少发生一个的概率
P(A+B)=P(A)+P(B)-P(AB)
P(A)=(P(A+B)-P(B))/(1-P(B))
然后你直接用上式计算父亲对儿子，儿子对父亲的转移，就OK
考虑一个点不连通的概率
设f[x]表示x不通电的概率
考虑x的儿子对它的贡献，那么
$f[x] = (1 - p[x]) * \pi (1-(1-f[v]) * w)$
,v为x的儿子，w为边连通的概率。
考虑v的父亲x对v的贡献，我们设k
为x除去v这个点连通的概率，那么
$P = 1 - \frac{f[x]}{(1 - (1 - f[v]) * w)} 。$
于是$f[v] *= 1 - P * w $
对于上式，两边dfs求出$f[x]$
$ans=\sum_{i = 1}^{n}1-f[i]$
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-8
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x;
}
const int maxn = 500007;
struct Node {
int v,next;double w;
} edge[maxn << 1];
int head[maxn],num = 0;
void add_edge(int u,int v,double w) {
edge[++ num].v = v;edge[num].w = w;edge[num].next = head[u];head[u] = num;
}
int n; double p[maxn],f[maxn];
void dfs(int x,int fa) { //自下而上，不考虑父节点影响
f[x] = 1 - p[x];
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v == fa)continue;
dfs(v,x);
f[x] *= 1 - (1 - f[v]) * edge[i].w;
}
}
void dfs2(int x,int fa) {
double k;
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v == fa)continue;
k = 1 - f[x] / (1 - (1 - f[v]) * edge[i].w);
if(k > eps)f[v] *= 1 - (k * edge[i].w);
dfs2(v,x);
}
}
int main() {
n = read();
for(int u,v,w,i = 1;i < n;++ i) {
u = read(),v = read(),w = read();
double tmp = 1.0 * w / 100;
add_edge(u,v,tmp);add_edge(v,u,tmp);
}
for(int w,i = 1; i <= n;++ i) {
w = read();
p[i] = 1.0 * w / 100;
}
dfs(1,0);
dfs2(1,0);
double ans = 0;
for(int i = 1;i <= n;++ i) ans += 1 - f[i];
printf("%.6lf",ans);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9276711.html
