BZOJ3566:[SHOI2014]概率充电器 树形期望dp
思路:
膜拜的bill125神犇的题解.
(首先将树转化为有根树)
首先求一个节点能够充上电的的概率是很不容易的,我们转化为求一个结点不能充上电的概率,那么分为两部分,分别是这个结点的子节点不能给这个结点充电的概率和这个结点的父亲不能给这个结点充电的概率.
令这两个东西分别为fi,0,fi,1.
首先我们dfs一遍求出fi,0.
fi,0=(1−qi)Πj∈son(i)(fson,0+(1−fson,0)∗(1−pEdge(i,j)))
这一次我们首先考虑的是每个节点对祖先的贡献.
接下来考虑每个节点对子树中节点的贡献.
令x的父亲为pax,令t表示在除了x之外的节点的影响下没有被充电的概率,我们有:
t=fpax,0/(fx,0+(1−fx,0)∗(1−pEdge(x,pax)))∗fpax,1
fx,1=t+(1−t)∗(1−pEdge(x,pax))
(注意特判t不存在的情况)
那么最终节点i被充电的概率就是gi=1−fi,0∗fi,1,则:
ans=n∑i=1gi
这样就可以O(n)出解了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<cstdio>#include<cctype>#include<cstring>#include<iostream>#include<algorithm>using namespace std; typedef double f2; #define N 500010 int head[N],next[N<<1],end[N<<1],pa[N];f2 p[N<<1],pp[N];inline void addedge(int a,int b,f2 _p){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,p[q++]=_p;}inline void make(int a,int b,f2 _p){addedge(a,b,_p),addedge(b,a,_p);} f2 f[N][2];void dfs1(int x,int fa){ for(int j=head[x];j;j=next[j]){ if(end[j]!=fa){ pp[end[j]]=p[j],pa[end[j]]=x,dfs1(end[j],x); f[x][0]*=f[end[j]][0]+(1-f[end[j]][0])*(1-pp[end[j]]); } }}void dfs2(int x,int fa){ f2 t,_p; for(int j=head[x];j;j=next[j]){ if(end[j]!=fa){ t=f[end[j]][0]+(1-f[end[j]][0])*(1-pp[end[j]]); _p=t<1e-6?0:f[x][1]*f[x][0]/t; f[end[j]][1]=_p+(1-_p)*(1-pp[end[j]]); dfs2(end[j],x); } }}int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif int n;cin>>n; register int i,j;int a,b,x;for(i=1;i<n;++i)scanf("%d%d%d",&a,&b,&x),make(a,b,x/100.0); for(i=1;i<=n;++i)scanf("%d",&x),f[i][0]=1-x/100.0; dfs1(1,-1),f[1][1]=1,dfs2(1,-1); f2 res=0;for(i=1;i<=n;++i)res+=1-f[i][0]*f[i][1]; printf("%.6lf",res); return 0;} |
评论 (0)