前情提要：最近大佬們都在寫題解，只有我在咕咕咕。QAQ；明明我都把flag寫出來辣，dalao們沒看見，然后就被嘲諷了,QAQ

洛谷

樹形DP+期望（講了兩次，菜雞的我才做ＱＡＱ）

---

?

首先，每個充電元件和電源之間的關系可以用一棵樹來表示。通過感性分析可知，每個元件對于期望的貢獻就是0/1。（進入狀態(tài)就是1，否則就是0）。故而進入充電狀態(tài)的元件的個數(shù)的期望就是元件進入充電狀態(tài)的概率。

那么設元件進入充電狀態(tài)的概率為${\large{p[]}}$，我們要求的就轉(zhuǎn)化為${\large{\sum_{i=1}^np[i]}}$

然后我們就開始設計狀態(tài)來求解${\large{p[]}}$。顯然我們可以知道，一個點被充電只有兩種可能：自己被自己所在的子樹(包括自己)充上，自己被自己的父親充上

然后開始思考，，，，，一萬年之后?我們發(fā)現(xiàn)，如果設計的狀態(tài)是被充上電的話，狀態(tài)就很難寫，所以我們決定把狀態(tài)設為不會被充上電的概率，即

${\large{f[]}}$不會被自己所在子樹充上電的概率，${\large{g[]}}$不會被自己的父親充上電的概率

同時我們設已知量導線導電的概率為${\large{val[][]}}$表示${\large{i->j}}$可以充電的概率。用${\large{q[]}}$表示自己被自己充上電的概率。

首先求看起來比較容易求的${\large{f[]}}$

不被自己所在的子樹充上電，要滿足${\color{red}{既不會}}$自己被自己充上電，${\color{red}{又不會}}$被自己的兒子充上電。不被自己的兒子充上電又分兩種情況：第一種是兒子自己本身就沒有電，第二個是兒子有點但是導線沒有電。所以dp式子如下：

${\large{f[i]=\prod_{v\in{son[i]}}(1-q[i])*(f[v]*(1-val[i][v])+f[v])}}$

然后再來看看比較難求的不會被自己父親充上電的概率${\large{g[]}}$

不會被自己的父親充上電有兩種情況，第一種是自己的父親沒有電，即自己的父親既不會被自己的所在的子樹充上電，又不會被自己的父親充上電。第二種情況就是父親有電，但是鏈接父親和自己的導線不能導電。同時要注意的一個點就是我們問的是某個點會不會被自己的父親充上電，所以這個點自己${\color{red}{沒電}}$。故，當我們在求解父親會不會被自己兒子充上電的時候，要注意除去該兒子有電的概率。由于父親沒電的概率要一個長式子來表示，所以我們先設父親沒電的概率為${\large{Q}}$，則有DP式子如下：

${\large{Q=\frac{g[i]*f[i]}{f[v]+(1-f[v])*(1-val[i][v])},v\in{son[i]}}}$

${\large{g[v]=Q+(1-Q)*(1-val[i][v])}}$

最后的答案就是這個點既不會不被自己所在的子樹充上電，又不會不被自己的父親節(jié)點充上電的概率和

剩下的就是樹形DP的板子式的寫法了（不過要注意浮點數(shù)）

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 namespace the_Death{ 6 const int maxn=5e5+100;bool vis[maxn]; 7 int head[maxn],ver[maxn<<1],nxt[maxn<<1],tot,n,x,y,pre[maxn]; 8 double edge[maxn<<1],z,f[maxn],q[maxn],g[maxn],Q,ans; 9 inline void add(int x,int y,double z){ 10 ver[++tot]=y,nxt[tot]=head[x]; 11 head[x]=tot;edge[tot]=z*1.00/100.0; 12 } 13 inline void dfs(int x,int fa){ 14 pre[x]=fa;f[x]=(1-q[x]); 15 for(register int i=head[x];i;i=nxt[i]){ 16 int y=ver[i]; 17 if(y==fa||vis[y]) continue; 18 vis[y]=1;dfs(y,x); 19 f[x]*=((1.0-f[y])*(1-edge[i])+f[y]); 20 } 21 } 22 inline void solve(int x){ 23 for(register int i=head[x];i;i=nxt[i]){ 24 int y=ver[i]; 25 if(vis[y]||y==pre[x]) continue; 26 vis[y]=1; 27 Q=(g[x]*f[x])/(1.0*(f[y]+(1-f[y])*(1-edge[i]))); 28 g[y]=Q+(1-Q)*(1-edge[i]); 29 solve(y); 30 } 31 } 32 int main(){ 33 scanf("%d",&n);g[1]=1; 34 for(register int i=1;i<n;i++) 35 scanf("%d%d%lf",&x,&y,&z), 36 add(x,y,z),add(y,x,z); 37 for(register int i=1;i<=n;i++) 38 scanf("%lf",&z),q[i]=z/100.0; 39 //它給的是直接充電的概率*100，所以要除回去 40 dfs(1,0); 41 memset(vis,0,sizeof(vis)); 42 solve(1); 43 for(register int i=1;i<=n;i++) 44 ans+=1.0-f[i]*g[i]; 45 printf("%.6lf",ans);return 0; 46 } 47 } 48 int main(){ 49 the_Death::main();system("pause"); 50 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/fallen-down/p/11560039.html

總結

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

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