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); PRintf("%.6lf",ans); return 0;}

上一篇：人工智能和新科技革命

下一篇：用链表或者数组实现一个栈