首页 > 其他 > 详细

BZOJ 3566 概率充电器

时间:2019-03-22 20:59:56      阅读:116      评论:0      收藏:0      [点我收藏+]

先假设只能向上导电,这样我们可以DFS一遍得到树根带电的概率,得到 \(O(n^2)\) 做法

对于非树根点,考虑一下(父子间)变化量,O(n)

注意不要除0,将要除0时特殊处理一下

#include <cstdio>
#include <cctype>

const double eps=1e-10;
const int MAXN=500111;

char gc(){
    static char buf[1<<16], *s=buf, *t=buf;
    if(s==t)    t=(s=buf)+fread(buf, 1, 1<<16, stdin);
    if(s==t)    return EOF;
    return *s++;
}

int read(){
    int x=0, f=1;char ch=gc();
    while(!isdigit(ch)) {if(ch=='-')f=-f;ch=gc();}
    while(isdigit(ch))  {x=x*10+(ch-'0');ch=gc();}
    return x*f;
}

int N;

struct Vert{
    int FE;
    double p, f, t, s;
    double cal(double k){
        return p+(1.0-p)*(1.0-k);
    }
} V[MAXN];

struct Edge{
    int y, next;
    double p;
} E[MAXN<<1];

int Ecnt;

void addE(int a, int b, double c){
    ++Ecnt;
    E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;E[Ecnt].p=c;
}

void DFS(int at, int f){
    V[at].t=1.0;
    for(int k=V[at].FE, to;k;k=E[k].next){
        to=E[k].y;
        if(to==f)   continue;
        DFS(to, at);
        V[at].t*=1.0-E[k].p*V[to].f;
    }
    V[at].f=V[at].cal(V[at].t);
}

void DFS(int at, double pf, int f){
    V[at].t*=(1.0-pf);
    V[at].s=V[at].cal(V[at].t);
    for(int k=V[at].FE, to;k;k=E[k].next){
        to=E[k].y;
        if(to==f)   continue;
        DFS(to, (1.0-V[to].f<eps)?0.0:E[k].p*V[at].cal(V[at].t/(1.0-E[k].p*V[to].f)), at);
    }
}

int main(){
    
    N=read();
    
    for(int i=1, a, b, c;i<N;++i){
        a=read();b=read();c=read();
        addE(a, b, (double)(c)/100.0);
        addE(b, a, (double)(c)/100.0);
    }
    
    for(int i=1;i<=N;++i)   V[i].p=(double)(read())/(100.0);
    
    DFS(1, 0);
    DFS(1, 0.0, 0);
    
    //for(int i=1;i<=N;++i) printf("%lf ", V[i].s);
    //puts("");
    double Ans=0.0;
    for(int i=1;i<=N;++i)   Ans+=V[i].s;
    printf("%.6lf\n", Ans);
    
    return 0;
}

/*
3
1 2 50
1 3 50
50 0 0

*/

BZOJ 3566 概率充电器

原文:https://www.cnblogs.com/Pickupwin/p/BZOJ3566.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!