bzoj 3566: [SHOI2014]概率充電器概率dp+樹形dp

2019-11-06 06:03:14

字體：大中小

來源：轉載

供稿：網友

題意

有一棵樹，每個節點有一個自身通電的概率，每條邊有一個能夠導電的概率，求期望通電的節點個數。 n<=500000

分析

在某些題庫上提交居然爆棧了。。。

別人口中的傻逼題我居然做了辣么久，看來在期望這方面我還是有所欠缺啊。。。

一開始的想法是設f[i]表示i能夠通電，i的子樹的期望通電節點數，g[i]表示i不能通電的期望節點數。然后就推了半天沒推出來。。。

正解是這樣噠：大體思路就是求出每個節點通電的概率然后加起來。每個節點通電有三種情況： 1、自己通電 2、從子樹通電 3、從非子樹節點通電第一種情況很好求。對于第二種情況，我們設p[i]表示i通電的概率，那么遞推式為p[i]=p[i]+p[to]?pedge?(1?p[i]) $p[i]=p[i]+p[to]*p_{edge}*(1-p[i])$ 說一下自己的理解 p[i]就是原來自己的概率，p[to]?pedge表示子節點能通到i的概率，并且要保證i沒有被其他節點通電，所以要乘上一個(1?p[i]) $p[i]就是原來自己的概率，p[to]*p_{edge}表示子節點能通到i的概率，并且要保證i沒有被其他節點通電，所以要乘上一個(1-p[i])$ 對于第三種情況，我們就要從父親轉移到兒子，那么就要先把兒子對父親的影響去掉。由上面的遞推式可以得到 p[withoutson]=p[now]?p[son]?pedge1?p[son]?pedge $p[without son]=/frac{p[now]-p[son]*p_{edge}}{1-p[son]*p_{edge}}$

然后跟上面一樣轉移即可。注意特判分母為0的情況。

代碼

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 500005using namespace std;const double eps=1e-8;int cnt,last[N],n;struct edge{int to,next;double val;}e[N*2];double p[N],ans;void addedge(int u,int v,int val){ e[++cnt].to=v;e[cnt].val=1.0*val/100;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].val=1.0*val/100;e[cnt].next=last[v];last[v]=cnt;}void dfs1(int x,int fa){ for (int i=last[x];i;i=e[i].next) { if (e[i].to==fa) continue; dfs1(e[i].to,x); p[x]=p[x]+1.0*p[e[i].to]*e[i].val-1.0*p[x]*p[e[i].to]*e[i].val; }}void dfs2(int x,int fa){ ans+=p[x]; for (int i=last[x];i;i=e[i].next) { if (e[i].to==fa) continue; double t=(1.0-p[e[i].to]*e[i].val); if (t<=eps) p[e[i].to]=1; else { double tmp=1.0*(p[x]-p[e[i].to]*e[i].val)/(1.0-p[e[i].to]*e[i].val); p[e[i].to]+=1.0*tmp*e[i].val-1.0*p[e[i].to]*tmp*e[i].val; } dfs2(e[i].to,x); }}int main(){ //freopen("charger.in","r",stdin);freopen("charger.out","w",stdout); scanf("%d",&n); for (int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } for (int i=1;i<=n;i++) scanf("%lf",&p[i]),p[i]=1.0*p[i]/100; dfs1(1,0); dfs2(1,0);