3566: [SHOI2014]概率充電器

Description

著名的電子產(chǎn)品品牌 SHOI 剛剛發(fā)布了引領(lǐng)世界潮流的下一代電子產(chǎn)品——概率充電器:
“采用全新納米級加工技術(shù),實(shí)現(xiàn)元件與導(dǎo)線能否通電完全由真隨機(jī)數(shù)決定!SHOI 概率充電器,您生活不可或缺的必需品!能充上電嗎?現(xiàn)在就試試看吧!
”
SHOI 概率充電器由 n-1 條導(dǎo)線連通了 n 個(gè)充電元件。進(jìn)行充電時(shí),每條導(dǎo)線是否可以導(dǎo)電以概率決定,每一個(gè)充電元件自身是否直接進(jìn)行充電也由概率決定。
隨后電能可以從直接充電的元件經(jīng)過通電的導(dǎo)線使得其他充電元件進(jìn)行間接充電。
作為 SHOI 公司的忠實(shí)客戶,你無法抑制自己購買 SHOI 產(chǎn)品的沖動(dòng)。在排了一個(gè)星期的長隊(duì)之后終于入手了最新型號的 SHOI 概率充電器。
你迫不及待地將 SHOI 概率充電器插入電源——這時(shí)你突然想知道,進(jìn)入充電狀態(tài)的元件個(gè)數(shù)的期望是多少呢?

Input

第一行一個(gè)整數(shù):n。概率充電器的充電元件個(gè)數(shù)。充電元件由 1-n 編號。
之后的 n-1 行每行三個(gè)整數(shù) a, b, p,描述了一根導(dǎo)線連接了編號為 a 和 b 的
充電元件,通電概率為 p%。
第 n+2 行 n 個(gè)整數(shù):qi。表示 i 號元件直接充電的概率為 qi%。

Output

輸出一行一個(gè)實(shí)數(shù),為進(jìn)入充電狀態(tài)的元件個(gè)數(shù)的期望,四舍五入到六位小數(shù)

Sample Input

3
1 2 50
1 3 50
50 0 0

Sample Output

1.000000

HINT

對于 100%的數(shù)據(jù),n≤500000,0≤p,qi≤100。

---

傳送門 感覺還是挺有難度的一道題，但是似乎挺多人表示是水題，大概是我太弱了吧。。。 先補(bǔ)充一點(diǎn)概率論的概念：$$P(A+B)=P(A)+P(B)-P(A)\times P(B)\cdots \cdots ①$$將上面的式子變一下形我們可以得到$$P(A)=\frac {(P(A+B)-P(B))}{1-P(B)}\cdots \cdots ②$$ 其中$P(A+B)\Leftrightarrow P(A\bigcap B)=$A或B發(fā)生的概率；$P(AB)\Leftrightarrow P(A\bigcup B)=$A與B同時(shí)發(fā)生的概率； 然后再來看看這道題，一個(gè)充電元件被充電的條件為： 1）其子節(jié)點(diǎn)充電 2）其父節(jié)點(diǎn)充電 3）自身充電 設(shè)$f[k]$為節(jié)點(diǎn)$k$被子節(jié)點(diǎn)或自身充電的概率；$g[k]$為節(jié)點(diǎn)$k$被充電的總概率； 令$a=\sum _{edge_{k,v}}(f[v]\times egde.p)$即$k$被孩子充電的概率,其中$edge.p$為$k$與子節(jié)點(diǎn)間的通電概率 由$①$得$f[k]=q[k]+a-q[k]\times a$ 令$b=(g[father[k]]-f[k]\times?egde.p)/(1-f[k]\times?egde.p)$即$k$的父親給$k$充電的概率（由$②$）,其中$edge.p$為$k$與父節(jié)點(diǎn)間的通電概率 由$①$得$g[k]=f[k]+b\times edge.p-f[k]*b*edge.p$,其中$edge.p$為$k$與父節(jié)點(diǎn)間的通電概率 根據(jù)上述方程，兩次DFS就好辣！ 1 #include<cstring> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #define foru(i,x,y) for(int i=x;i<=y;i++) 6 #define fore(i,x) for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to) 7 using namespace std; 8 typedef double db; 9 const int N=1e6+10; 10 struct edge{int to,nxt;db w;}e[N*2]; 11 int head[N],siz[N],n,fa[N],ne; 12 db p[N],f[N],g[N],ans; 13 void add(int a,int b,db c){ 14 e[++ne]=(edge){b,head[a],c};head[a]=ne; 15 } 16 17 void dfsf(int k,int fa){ 18 fore(i,k){ 19 if(v==fa)continue; 20 dfsf(v,k); 21 f[k]=f[k]+f[v]*e[i].w-f[k]*f[v]*e[i].w; 22 } 23 } 24 25 void dfsg(int k,int fa){ 26 ans+=g[k]; db t=0; 27 fore(i,k){ 28 if(v==fa)continue; 29 if(1-e[i].w*f[v]<=1e-8)g[v]=1; 30 else{ 31 t=(g[k]-f[v]*e[i].w)/(1-f[v]*e[i].w); 32 g[v]=f[v]+t*e[i].w-f[v]*t*e[i].w; 33 } 34 dfsg(v,k); 35 } 36 } 37 38 int main(){ 39 int u,v,w; 40 db P; 41 scanf("%d",&n); 42 foru(i,1,n-1){ 43 scanf("%d%d%d",&u,&v,&w); 44 P=(db)w/100; 45 add(u,v,P);add(v,u,P); 46 } 47 foru(i,1,n){ 48 scanf("%lf",&p[i]); 49 f[i]=(p[i]/100); 50 } 51 dfsf(1,0); 52 g[1]=f[1]; 53 dfsg(1,0); 54 printf("%.6lf\n",ans); 55 }

---

總結(jié)：寫的時(shí)候考慮的情況不全、概率論公式寫錯(cuò)了，GG，最后還是看了題解。

轉(zhuǎn)載于:https://www.cnblogs.com/y-m-y/p/6893852.html

總結(jié)

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

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