bzoj 3566: [SHOI2014]概率充电器 树形DP

2019-04-14 09:03发布

站内文章 / 模拟电子
9685 0 1095
首先普及一个概率公式 P(A+B)=P(A)+P(B)-P(AB) 题意：一些充电元件和导线构成一棵树，充电元件是否能充电有2种情况， 1、它自己有qi%的概率充电 2、与它相邻的元件通过导线给它充电（导线有p%的概率导通） 求最终充了电的元件的期望 题解：首先可以将元件能否充电分成3种情况考虑， 1、它自己给自己充好了电 2、它的儿子方向给它传送了电 3、它的父亲方向给它传送了电。 对于1，题目已经给出可以直接赋值， 对于2，可以通过一次树的深度遍历求得。pson[now]=pson[now] + pson[to]*edge_p - pson[now]*pson[to]*edge_p 对于3，麻烦一点，因为2中我们已经求得当前点(now)的儿子们给当前点的贡献，现在要求当前点给它的某个儿子(to)的贡献，这里要计算的话，就必须要排除之前to->now的，（想想若2中计算了to->now的概率，现在又要计算now->to的概率，明显出现了循环）具体公式推导见代码
/* 设y = now点除了从to点来的电 的充电概率，dp[i]表示i点的充电概率，pson[i]表示在i的子树中，i的充电概率 pson[to]*p + y - pson[to]*p*y=dp[now] (1-pson[to]*p)*y=dp[now]-pson[to]*p y=(dp[now]-pson[to]*p)/(1-pson[to]*p); dp[to]=pson[to] + y*p - pson[to]*y*p; */ #include #include #include #include #include #include using namespace std; #define eps 1e-6 struct edge { int to,next; double p; }e[2000000]; int head[500005],en; double pson[500005]; double dp[500005]; double ans=0; void add(int a,int b,double c) { e[en].to=b; e[en].p=c; e[en].next=head[a]; head[a]=en++; } void dfs(int now,int fa) { for(int i=head[now];~i;i=e[i].next) { int to=e[i].to;double p=e[i].p; if(to==fa) continue; dfs(to,now); pson[now]=pson[now]+pson[to]*p-pson[now]*pson[to]*p; } } bool cmp(double a,double b) { return fabs(a-b)

热门文章