OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SHOI2014】概率充电器

【题目描述】

著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:

“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”

SHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。

随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为SHOI公司的忠实客户,你无法抑制自己购买SHOI产品的冲动。在排了一个星期的长队之后终于入手了最新型号的SHOI概率充电器。

你迫不及待地将SHOI概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

【输入】

第一行一个整数:n。概率充电器的充电元件个数。充电元件由1-n编号。

之后的n-1行每行三个整数a,b,p,描述了一根导线连接了编号为a和b的充电元件,通电概率为p%。

第n+2行n个整数qi,表示i号元件直接充电的概率为qi%。

【输出】

输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到6位小数。

【输入样例】

5

1 2 90

1 3 80

1 4 70

1 5 60

100 10 20 30 40

【输出样例】

4.300000

【数据范围】

对于100%的数据,n≤500000,0≤p,qi≤100。

【题解】

写题解的一大好处:借(chao)鉴(xi)别人思(dai)路(ma)时可以认真梳理一遍。

虽然是一棵树,但直接DP每个点可以被充电的概率很不好算,原因在于一个点被充电无非两种情况:从父节点方向导电,或在以这个点为根的子树内被充电,而这两种情况无论先计算那一种都会出现算重的情况,即一个点给它的父亲充电这部分的概率在父亲给他充电时被重复计算(或者倒过来被重复计算)。也许有好的解决方法?总之我尝试这么做WA完了……

我们反过来考虑,既然DP每个点可以被充电的概率不好算,那就DP不可以被充电的概率呗。先考虑以点x为根的子树里x不充电的概率s[x],自身不充电的概率为1-p[x],假如它有一个儿子y,考虑两个独立的情况:以点y为根的子树里y不充电的概率是s[y],y充电但x->y不导电的概率是(1-s[y])*(1-edge[x->y])。显然这两种情况应该相加,再全部相乘就是x不充电的概率s[x]。

再来考虑父节点方向,我们设t为x对它的父亲fa不能充电贡献的概率(SMG),根据上面的算法,则t=s[x]+(1-s[x])*(1-edge[fa->x]),因此s[fa]/t就表示除x以外以fa为根的子树内f不被充电的概率,再乘上fa不被父节点方向充电的概率f[fa],我们得到了除去x后fa不被充电的概率。再延用刚才的思路,令q=s[fa]/t*f[fa]表示这个概率,再延用刚才的思路,分为这种情况下fa不被充电和fa被充电但fa->x不导电,因此f[x]=q+(1-q)*(1-edge[fa->x])。

答案显然就是∑1-s[i]*f[i]~

不重不漏地计算概率简直是一门艺术啊,主要是要多思考、多转化,而积累一些经验也相当必要。像这题里用到的取补集和概率去重都是很常见的转化方法,而期望是概率相关的加权平均数这一点也为计算答案提供了依据。

【代码】

maya大家神得无法直视时,我却傻得无法直视QAQ

http://paste.ubuntu.com/10878888/

评论

© OI技术宅 | Powered by LOFTER