A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3566 概率充电器 概率$dp$
发表于: | 分类: Oi | 评论:0 | 阅读:43

现在给出一个树形的电路,共有$n$个节点,节点$i$有$q_i$的概率自动被充电,树边$j$有$p_j$的概率流通电流,求进入充电状态的点的个数的期望

按照树形$dp$的套路,我们把这个东西分成两部分
一部分是这个节点被他的儿子点亮或者自己点亮,另外一个部分就是他被他的父亲点亮,然后这就变成了两遍“扭一扭”的常见题目了

第一次树形$dp$我们求出$f(i)$,表示$i$不被他的儿子点亮的概率,显然分为儿子不亮和边不通两种情况,儿子不亮就是$f(to)$,儿子亮但是边不通是$(1-q_i)*(1-f(to))$,只要这两种情况
第二次树形$dp$算出$g(i)$,表示$i$不被他父亲点亮的概率,首先显然有$g(root) = 1$,然后从上面转移到下面又可以讨论,一种是上面根本就不亮,另外一种是上面亮但是边不通,对应分别是$g(fa_i)$ 和 $(1-g(fa_i))·(1-q_i)$
显然刚才说的两部分是互相完全不互相影响的独立事件
最后就可以直接算了,式子即
$$ans=\sum\limits^{n}_{i=1}{(1-f(i)*g(i))}$$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 500000+5;
const int M = N << 1;
const double eps = 1e-7;
using namespace std;

int head[N];

struct graph
{
    int next,to;
    double val;
    graph () {}
    graph (int _next,int _to,double _val)
    :next(_next),to(_to),val(_val){}    
}edge[M];

inline void add(int x,int y,double z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z);
    head[y] = cnt;
}

double F[N][2];

void DFS1(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa)
            {
                DFS1(edge[i].to,x);
                F[x][0] *= (F[edge[i].to][0] + (1.0-F[edge[i].to][0])*(1.0-edge[i].val));
            }
}

void DFS2(int x,int fa)
{
    double tmp1,tmp2;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa)
        {   
            tmp2 = (F[edge[i].to][0] + (1.0-F[edge[i].to][0])*(1.0-edge[i].val));
            tmp1 = tmp2 < eps ? 0 : F[x][0]/tmp2*F[x][1];
            F[edge[i].to][1] = tmp1 + (1.0-tmp1)*(1.0-edge[i].val);
            DFS2(edge[i].to,x);
        }
}

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read(),tt;

    for(int i=1;i<n;++i){
        int x = read(), y = read(), z = read();
        add(x,y,0.01*z);
    }

    for(int i=1;i<=n;++i)
    {
        tt = read();
        F[i][0] = 1.0-0.01*tt;
    }
    DFS1(1,-1); F[1][1] = 1; DFS2(1,-1);
    double ans = 0.0;
    for(int i=1;i<=n;++i) ans += 1.0-F[i][0]*F[i][1];
    printf("%.6lf",ans);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP