BZOJ 3566

樹形$dp$ + 概率期望。

每一個點的貢獻都是$1$，在本題中期望就等于概率。

發現每一個點要通電會在下面三件事中至少發生一件：

1、它自己通電了。

2、它的父親給它通電了。

3、它的兒子給它通電了。

那么我們設$f_i$表示它的父親給它通電的概率，$g_i$表示它的子樹中給它通電的概率，那么最后的答案$\sum_{i = 1}^{n}f_i + g_i - f_i * g_i = \sum_{i = 1}^{n}1 - (1 - f_i) * (1 - g_i)$。

感覺好麻煩，直接把$f_i$和$g_i$設成不通電的概率好了。

先考慮計算$g$。

假設每個點$i$自己通電的概率是$a_i$，一條連接著$x$和$y$的邊通電的概率是$val(x, y)$，那么$g_x = (1 - a_x)\prod_{y \in son(x)}(g_y + (1 - g_y) * (1 - val(x, y)))$。

因為如果一個點不從自己的子樹中得到電，那么它自己一定沒有電，然后對于每一個兒子，要么不通電，要么通了電但是這條邊是不通電的，電量傳遞不上來。

然后考慮計算$f$，對于一對父子關系的點$(x, y)$，我們發現要么$x$不帶電，要么$x$帶了電但是這條邊傳遞不過來，那么$x$不帶電的概率$P = \frac{f_x * g_x}{g_y + (1 - g_y) * (1 - val(x, y))}$，

這時候我們默認$y$是不帶電的，但是我們在計算$g_x$的時候多算了$y$的貢獻，所以要除掉，然后$f_y = P + (1 - P) * (1 - val(x, y))$。

時間復雜度$O(n)$。

Code：

#include <cstdio> #include <cstring> using namespace std; typedef double db;const int N = 5e5 + 5;int n, tot = 0, head[N]; db a[N], f[N], g[N];struct Edge {int to, nxt;db val; } e[N << 1];inline void add(int from, int to, db val) {e[++tot].to = to;e[tot].val = val;e[tot].nxt = head[from];head[from] = tot; }inline void read(int &X) {X = 0; char ch = 0; int op = 1;for(; ch > '9' || ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op; }void dfs1(int x, int fat) {g[x] = 1 - a[x];for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(y == fat) continue;dfs1(y, x);g[x] *= (g[y] + (1 - g[y]) * (1 - e[i].val));} }void dfs2(int x, int fat, int inEdge) {if(!fat) f[x] = 1.0;else {db p = g[fat] * f[fat] / (g[x] + (1 - g[x]) * (1 - e[inEdge].val));f[x] = p + (1 - p) * (1 - e[inEdge].val);}for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(y == fat) continue;dfs2(y, x, i);} }int main() { // freopen("2.in", "r", stdin); read(n);for(int x, y, v, i = 1; i < n; i++) {read(x), read(y), read(v);db val = 1.0 * v / 100.0;add(x, y, val), add(y, x, val);}for(int i = 1; i <= n; i++) {int v; read(v);a[i] = 1.0 * v / 100.0;}dfs1(1, 0);dfs2(1, 0, 0);/* for(int i = 1; i <= n; i++)printf("%f ", f[i]);printf("\n");for(int i = 1; i <= n; i++)printf("%f ", g[i]);printf("\n"); */db ans = 0;for(int i = 1; i <= n; i++)ans += (1 - g[i] * f[i]);printf("%.6f\n", ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/CzxingcHen/p/9875864.html

總結

以上是生活随笔為你收集整理的Luogu 4284 [SHOI2014]概率充电器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。