P4284 [SHOI2014]概率充電器

題目描述

著名的電子產(chǎn)品品牌SHOI 剛剛發(fā)布了引領(lǐng)世界潮流的下一代電子產(chǎn)品—— 概率充電器：

“采用全新納米級(jí)加工技術(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í)客戶，你無(wú)法抑制自己購(gòu)買 SHOI 產(chǎn)品的沖動(dòng)。在排了一個(gè)星期的長(zhǎng)隊(duì)之后終于入手了最新型號(hào)的 SHOI 概率充電器。你迫不及待地將 SHOI 概率充電器插入電源——這時(shí)你突然想知道，進(jìn)入充電狀態(tài)的元件個(gè)數(shù)的期望是多少呢？

輸入輸出格式

輸入格式：

第一行一個(gè)整數(shù)：\(n\)。概率充電器的充電元件個(gè)數(shù)。充電元件由 \(1-n\) 編號(hào)。

之后的 \(n-1\) 行每行三個(gè)整數(shù)\(a,b,p\) ，描述了一根導(dǎo)線連接了編號(hào)為 \(a\) 和 \(b\) 的 充電元件，通電概率為\(p\%\)。

第 \(n+2\) 行 \(n\) 個(gè)整數(shù)：\(q_i\)。表示 \(i\) 號(hào)元件直接充電的概率為 \(q_i\%\)。

輸出格式：

輸出一行一個(gè)實(shí)數(shù)，為能進(jìn)入充電狀態(tài)的元件個(gè)數(shù)的期望，四舍五入到小數(shù)點(diǎn)后6位小數(shù)。

說(shuō)明

對(duì)于\(30\%\)的數(shù)據(jù)，\(n≤5000\)。

對(duì)于\(100\%\)的數(shù)據(jù)，\(n≤500000\)，\(0≤p,q_i≤100\)。

---

果然一做期望題就暴露自己腦子蠢的事實(shí)了=-=

首先我讀錯(cuò)題了，但是我覺得不能怪我啊，難道題目說(shuō)的不就是只有自己激發(fā)的才能傳火給別人嘛...

然后我花了好久才發(fā)現(xiàn)這個(gè)題就是在算概率。

每個(gè)點(diǎn)可以從所有其他點(diǎn)獲取傳火概率，做一個(gè)換跟dp就行了，具體的

\(dp_i\)先處理出子樹\(i\)的貢獻(xiàn)，然后直接換跟做就可以了。

需要注意的地方，傳火的時(shí)候要減去兩個(gè)都有，換跟中有一個(gè)類似退背包的過程需要處理分母為0

---

Code:

#include <cstdio> #include <cmath> const int N=5e5+10; const double eps=1e-8; int head[N],to[N<<1],Next[N<<1],cnt; double dp[N],ans,edge[N<<1]; void add(int u,int v,double w) {to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt; } void dfs1(int now,int fa) {for(int v,i=head[now];i;i=Next[i])if((v=to[i])!=fa){dfs1(v,now);dp[now]=dp[now]+dp[v]*edge[i]-dp[now]*dp[v]*edge[i];} } void dfs2(int now,int fa,double p) {dp[now]=dp[now]+p-dp[now]*p;ans+=dp[now];for(int v,i=head[now];i;i=Next[i])if((v=to[i])!=fa){if(fabs(dp[v]*edge[i]-1)<eps) p=dp[now];else p=(dp[now]-dp[v]*edge[i])/(1-dp[v]*edge[i]);dfs2(v,now,p*edge[i]);} } int main() {int n;scanf("%d",&n);for(int u,v,w,i=1;i<n;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,1.0*w/100),add(v,u,1.0*w/100);}for(int i=1;i<=n;i++) scanf("%lf",dp+i),dp[i]/=100.0;dfs1(1,0);dfs2(1,0,0);printf("%.6lf\n",ans);return 0; }

---

2019.1.13

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/10262582.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

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

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