解题：SHOI 2014 概率充电器

显然就是在求概率，因为期望乘的全是1.。。。然后就推推推啊

设$fgg[i]$表示这个点父亲没给他充上电的概率，$sgg[i]$表示这个点子树(和它自己)没给他充上电的概率，然后这个点没充上电的概率就是$fgg[i]*sgg[i]$

我们发现我们在树上转移的话$fgg$是依赖自己的$sgg$向儿子转移的，那我们先把$sgg$求出来，下面设$suc[i]$表示$i$这个点充上电的概率，$lnk[i][j]$表示连接$i$和$j$的导线能通电的概率

$sgg[i]=(1-suc[i])\prod_{g∈son_i}(sgg[g]+(1-sgg[g])*(1-lnk[i][g]))$

就是说首先自己不能充电，同时儿子也都不能给自己充电。所以每个儿子要么自己不能充电(这时不管导线)，要么能充电但是导线坏了，我们为了下面方便写不妨对每个儿子记录下这个儿子g gg的概率$p[g]$(即$(sgg[g]+(1-sgg[g])*(1-lnk[i][g]))$这一坨)

然后求$fgg$，这里我们先把每个点针对每个儿子$g$时自己不能给儿子充电的概率$P$求出来

$P=fgg[nde]*sgg[nde]/p[g]$

(在儿子g gg的所有情况$p[g]$中，因为父亲节点gg的原因有$fgg[nde]*sgg[nde]$这么多)

然后和上面一样可以求出来$fgg[g]$

$fgg[g]=P+(1-P)*(1-lnk[i][g])$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=1e6+;

 int p[N],noww[M],goal[M],n,t1,t2,cnt;

 double val[M],pos[N],sgg[N],fgg[N],mem[N],t3,ans;

 void Link(int f,int t,double v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 void Gettre(int nde,int fth)

 {

     sgg[nde]=-pos[nde];

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             int g=goal[i]; Gettre(g,nde);

             mem[g]=sgg[g]+(-sgg[g])*(-val[i]);

             sgg[nde]*=mem[g];

         }

 }

 void Getans(int nde,int fth)

 {

     ans-=sgg[nde]*fgg[nde];

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             int g=goal[i];

             double fag=sgg[nde]*fgg[nde]/mem[g];

             fgg[g]=fag+(-fag)*(-val[i]),Getans(g,nde);

         }

 }

 int main()

 {

     scanf("%d",&n),ans=n;

     for(int i=;i<n;i++)

     {

         scanf("%d%d%lf",&t1,&t2,&t3);

         Link(t1,t2,t3/),Link(t2,t1,t3/);

     }

     for(int i=;i<=n;i++)

         scanf("%lf",&pos[i]),pos[i]/=;

     Gettre(,),fgg[]=,Getans(,),printf("%.6f",ans);

     return ;

 }

巴特西

解题：SHOI 2014 概率充电器

最新文章

热门文章