博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
P4284 [SHOI2014]概率充电器
阅读量:7170 次
发布时间:2019-06-29

本文共 1473 字,大约阅读时间需要 4 分钟。

首先根据那啥啥期望的线性性,被充电原件的期望个数等于所有原件被充电的概率之和,于是我们考虑如何计算每一个原件被充电的概率

首先自己被充电和被导电两个概率是互相独立的,计算还得容斥很麻烦,于是我们考虑转为计算每个原件不会被导电的概率。一个原件不导电就是自己没电,别的节点也不会给它电。而别的节点的情况也分为两类,一是自己就没电,二是自己有电但边不导电而这两个事件是互相独立的

我们先用树形dp计算出一个点不会被子树内的点导电的概率是多少,设\(dp_i\)表示点\(i\)不导电的概率,\(P_i\)表示点\(i\)导电概率,\(val_i\)表示这条边导电的概率,则\(dp_u=(1-P_u)\prod dp_v+(1-dp_v)(1-val_i)\)

然后考虑\(i\)不会被子树外的点充上电的概率,设\(fa_i\)为点\(i\)不会被父亲充电的概率,那么点\(i\)不会被充电的概率就是\(fa_i*dp_i\),即父亲和子树都不会使它充上电。

然后考虑怎么转移,比方说\(u\)\(v\)的父亲,那么\(v\)不会被\(u\)充电的情况就是\(u\)没电或有电但边不导电。如何计算不考虑\(v\)的子树时\(u\)不导电的概率?因为转移是通过乘法原理转移的,所以只要把\(v\)\(u\)的贡献除去即可,也就是说只要用\(u\)不会被充电的总概率除以\(v\)不会使\(u\)充上电的概率即可

于是只要两边dfs,一遍求\(dp\),一遍求\(fa\)就可以了

如果有没讲清楚的地方可以看代码,代码应该还蛮好理解的

//minamoto#include
using namespace std;typedef double db;const int N=5e5+5;int head[N],Next[N<<1],ver[N<<1],tot;db edge[N<<1];inline void add(int u,int v,db e){ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;}db son[N],fa[N],st[N],res,p;int n;void dfs1(int u,int fat){ son[u]=1.0-st[u]; for(int i=head[u];i;i=Next[i]){ int v=ver[i];if(v==fat)continue;dfs1(v,u); son[u]*=son[v]+(1.0-son[v])*(1.0-edge[i]); }}void dfs2(int u,int fat){ for(int i=head[u];i;i=Next[i]){ int v=ver[i];if(v==fat)continue; p=fa[u]*son[u]/(son[v]+(1.0-son[v])*(1.0-edge[i])); fa[v]=p+(1.0-p)*(1.0-edge[i]);dfs2(v,u); }}int main(){// freopen("testdata.in","r",stdin); scanf("%d",&n); for(int i=1,u,v,e;i

转载于:https://www.cnblogs.com/bztMinamoto/p/9963227.html

你可能感兴趣的文章
zabbix使用msmtp&&mutt搭建邮件告警服务
查看>>
USB抓包工具--Bus Hound的使用方法详解
查看>>
location of android sdk has not been setup in the preference
查看>>
Centos7 二进制安装mysql5.7
查看>>
Centos7之Nginx的两种工作模式
查看>>
Java之品优购课程讲义_day18(3)
查看>>
rpm,yum,权限
查看>>
更新yum到 163
查看>>
Office 2019 & Office 2016 下载地址
查看>>
tomcat应用转到weblogic上时的问题
查看>>
国外程序员是如何准备面试的
查看>>
Zookeeper监控之——node-zk-browser
查看>>
我的友情链接
查看>>
10个最酷的linux单行命令
查看>>
myeclipse 10 在mac retina 屏幕下显示字体模糊解决方法
查看>>
创建自定义的指令
查看>>
javascript对象中判断属性
查看>>
git删除分支与合并分支
查看>>
Python元组
查看>>
HD TUNE以及所有其他硬盘检测工具都不能使用的情况
查看>>