【树形期望DP】BZOJ3566- [SHOI2014]概率充电器

【题目大意】

充电器由 n-1 条导线连通了 n 个充电元件。这n-1条导线均有一个通电概率p%，而每个充电元件本身有直接被充电的概率q[i]%。问期望有多少个充电元件处于充电状态？

【思路】

第一次做这种类型的题，还挺有意思的quq

显然这n个充电元件构成一棵树，考虑用树形DP。

我们用f1[i]表示当前元件仅仅因为直接充电或由孩子供电的概率，f2[i]表示当前元件处于充电状态的概率。

前铺两个知识点：对于两个相互独立的事件A、B，P(A+B)=P(A)+P(B)-P(A)*P(B)，P(A)=(P(A+B)-P(B))/(1-P(B))。（！！）

我们可以用两次dfs求出f1、f2的值。

①对于f1，由于树中叶子节点不存在孩子，f1[叶子结点]=q[叶子结点]，而对于非叶子节点，f1[i]=q[i]+∑f1[son]*p（注意这里的加法运算指代的是上述提到的概率加法）

②对于只由父亲贡献充电，我们考虑两个父子元件。对于父亲本身来说，给儿子充电的概率=总概率-儿子给自己充电的概率，pfa=f2[fa]-f1[now]*p(同样这里的减法用上面的概率加法)

f2[now]=f1[now]+pfa*p（同理这里的加法用的是上述的概率加法）

Over!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #define EPS (1e-8) 
 8 using namespace std;
 9 const int MAXN=500000+50;
10 struct node
11 {
12     int to;
13     double p;
14 };
15 vector<node> E[MAXN];
16 double q[MAXN],f1[MAXN],f2[MAXN],ans;
17 
18 void addedge(int a,int b,double p)
19 {
20     E[a].push_back((node){b,p});
21 }
22 
23 bool dcmp(double a)  
24 {  
25     return fabs(a-0)<EPS;  
26 }  
27 
28 void dfs1(int u,int fa)
29 {
30     for (int i=0;i<E[u].size();i++)
31     {
32         int to=E[u][i].to;
33         if (to!=fa) 
34         {
35             dfs1(to,u);
36             f1[u]=f1[u]+f1[to]*E[u][i].p-f1[u]*f1[to]*E[u][i].p;
37         }
38     }
39 }
40 
41 void dfs2(int u,int fa)
42 {
43     ans+=f2[u];
44     for (int i=0;i<E[u].size();i++)
45     {
46         int to=E[u][i].to; 
47         if (to!=fa)
48         {
49             if (dcmp(1.0-E[u][i].p*f1[to])) f2[to]=1.0;
50             else
51             {
52                 double tmp=(f2[u]-E[u][i].p*f1[to])/(1.0-E[u][i].p*f1[to]);
53                 f2[to]=f1[to]+tmp*E[u][i].p-f1[to]*tmp*E[u][i].p;
54             }
55             dfs2(to,u);
56         }
57     }
58 }
59 
60 void init()
61 {
62     int n;
63     scanf("%d",&n);
64     for(int i=0;i<n-1;i++)
65     {
66         int a,b;
67         double p;
68         scanf("%d%d%lf",&a,&b,&p);
69         addedge(a,b,p/100); 
70         addedge(b,a,p/100);
71     }
72     for (int i=1;i<=n;i++)
73     {
74         scanf("%lf",&q[i]);
75         f1[i]=q[i]/100;
76     }
77 }
78 
79 void solve()
80 {
81     dfs1(1,0);
82     f2[1]=f1[1];
83     dfs2(1,0);
84     printf("%.6lf",ans);
85 }
86 
87 int main()
88 {
89     init();
90     solve();
91     return 0;
92 }