SHOI2014 概率充电器（树形DP）（概率DP）（容斥）

SHOI2014 概率充电器（树形DP）（概率DP）（容斥）

​​传送门​​

好题啊！很明显要从子树算一遍，然后从父亲算一遍

然后从父亲走下来合并依然容斥合并

#include#define cs constusing namespace std;cs int N = 5e5 + 5;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}int first[N], nxt[N << 1], to[N << 1], tot; double w[N << 1];int n; double a[N], f[N];void add(int x, int y, double z){nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z; }void dfs1(int u, int fa){ f[u] = a[u]; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; dfs1(t, u); double p = w[i] * f[t]; f[u] = f[u] + p - f[u] * p; }}void dfs2(int u, int fa){ for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; double pa = f[t] * w[i]; if(pa < 1){ double pc = (f[u] - pa) / (1 - pa); double p = pc * w[i]; f[t] = f[t] + p - p * f[t]; } dfs2(t, u); }}int main(){ n = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); double z = read(); z = z/100.0; add(x, y, z); add(y, x, z); } for(int i = 1; i <= n; i++) a[i] = 1.0 * read() / 100.0; dfs1(1, 0); dfs2(1, 0); double ans = 0; for(int i = 1; i <= n; i++) ans += f[i]; printf("%.6lf", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。