正題

luogu 4284

---

題目大意

給你棵樹，第i個(gè)點(diǎn)自己通電的概率是$w_i$，第j條邊連接的兩個(gè)點(diǎn)之間通電的概率是$p_j$，問你通電的點(diǎn)個(gè)數(shù)的期望值

---

題目大意

設(shè)$f_i$為第i個(gè)點(diǎn)通電的概率，那么：

$$f_i=solv{e}_{j\in link\{i\}}(f_i,f_j?p_j)$$

即從該點(diǎn)轉(zhuǎn)一過來，$f_i$初值為$w_i$，solve為合并兩個(gè)概率

假設(shè)有x,y的概率由不同的兩個(gè)方法通電，那么p=1-(1-x)(1-y)=x+y-xy，即是solve

可以先按上述方法向父親轉(zhuǎn)移，計(jì)算出子節(jié)點(diǎn)傳遞到x的貢獻(xiàn)

.

然后可以再?gòu)母?jié)點(diǎn)向下計(jì)算父親向x的貢獻(xiàn)，但是要減去該點(diǎn)傳到父親再傳回去的概率，記不是由x傳遞過來，fa通電的概率為p，該點(diǎn)傳到父親的貢獻(xiàn)為g，那么有：

$$p+g?pg=f_{fa}$$

$$p(1?g)=f_{fa}?g$$

$$p=\frac{f_{fa}?g}{1?g}$$

這樣就可以得到其貢獻(xiàn)了

---

代碼

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 500050 using namespace std; int n, x, y, tot, h[N], fa[N], deg[N]; double z, ans, g[N], f[N]; queue<int>d; struct rec {int to, next;double p; }e[N<<1]; int read() {char x=getchar();int ds=0,fs=1;while (x<'0'||x>'9') {if (x=='-') fs=-1;x=getchar();}while (x>='0'&&x<='9') ds=(ds<<3)+(ds<<1)+x-48,x=getchar();return ds*fs; } void add(int x, int y, double z) {e[++tot].to = y;e[tot].p = z;e[tot].next = h[x];h[x] = tot;return; } double get(double x, double y)//計(jì)算 {return x + y - x * y; } void bfs() {d.push(1);while(!d.empty()){int x = d.front();d.pop();for (int i = h[x]; i; i = e[i].next){int v = e[i].to;if (v != fa[x]){fa[v] = x;deg[v]--;d.push(v);}}} } void bfs1() {for (int i = 1; i <= n; ++i)if (!deg[i])d.push(i);while(!d.empty()){int x = d.front();d.pop();if (!--deg[fa[x]]) d.push(fa[x]);for (int i = h[x]; i; i = e[i].next){int y = e[i].to;if (y != fa[x]){g[y] = f[y] * e[i].p;//從下向上傳f[x] = get(f[x], g[y]);}}}return; } void bfs2() {d.push(1);while(!d.empty()){int x = d.front();d.pop();for (int i = h[x]; i; i = e[i].next){int y = e[i].to;if (y != fa[x]){if (g[y] < 1.0) f[y] = get(f[y], ((f[x] - g[y]) / (1 - g[y])) * e[i].p);//從上到下傳，保證分母不為0d.push(y);}}} } /* void dfs1(int x, int fa)//dfs會(huì)暴棧 {f[x] = f[x] / 100.0;for (int i = h[x]; i; i = e[i].next){int y = e[i].to;if (y != fa){dfs1(y, x);g[y] = f[y] * e[i].p;f[x] = get(f[x], g[y]);}}return; } void dfs2(int x, int fa) {for (int i = h[x]; i; i = e[i].next){int y = e[i].to;if (y != fa){if (g[y] < 1.0) f[y] = get(f[y], ((f[x] - g[y]) / (1 - g[y])) * e[i].p);dfs2(y, x);}}return; } */ int main() {n = read();for (int i = 1; i < n; ++i){x = read();y = read();z = read() / 100.0;add(x, y, z);add(y, x, z);deg[x]++;deg[y]++;}for (int i = 1; i <= n; ++i)f[i] = read() / 100.0;bfs();bfs1();bfs2(); // dfs1(1, 0); // dfs2(1, 0);for (int i = 1; i <= n; ++i)ans = ans + f[i];printf("%.6lf", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【期望DP】概率充电器（luogu 4284）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。