OI技术宅

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

【ZJOI2015】地震后的幻想乡

【题目描述】

傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。

这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有n个地方,那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。

幻想乡这n个地方本来是连通的,一共有m条边。现在这m条边由于地震的关系,全部都毁掉了。每条边都有一个修复它需要花费的时间,第i条边所需要的时间为ei。地震发生以后,由于幽香是一位人生经验丰富,见得多了的长者,她根据以前的经验,知道每次地震以后,每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。

现在幽香要出去帮忙修复道路了。她可以使用一个神奇的大魔法,能够选择需要的那n-1条边,同时开始修复,那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边的ei值,然后再选择完成时间最小的方案。

幽香在走之前,她想知道修复完成的时间的期望是多少呢?

【输入】

第一行两个数n,m,表示地方的数量和边的数量。其中点从1到n标号。

接下来m行,每行两个数a,b,表示点a和点b之间原来有一条边。

这个图不会有重边和自环。

【输出】

一行输出答案,四舍五入保留6位小数。

【输入样例】

7 10

2 5

1 4

5 6

3 7

5 3

7 1

6 2

4 6

4 3

7 6

【输出样例】

0.617027

【数据范围】

对于15%的数据:n≤3。

另有15%的数据:n≤10,m=n。

另有10%的数据:n≤10,m=n(n-1)/2。

另有20%的数据:n≤5。

另有20%的数据:n≤8。

另有20%的数据:n≤10。

对于所有数据:m≤n(n-1)/2,n,m≥1。

【题解】

Orz冬令营原题(说的好像我当时听得很认真一样,明明是刚才补看的XD),题意大概是一张不超过10个点的简单图,每条边的边权是一个[0,1]之间等概率且互不相关的随机数,求这张图瓶颈生成树上最大边权值的期望值。

首先,由于边权在[0,1]均匀分布且互不相关,则边权两两不同的概率为1,并且没有重边和自环,所以我们只考虑每条边都独立的情况。假如瓶颈生成树上最大边为x,则只选择小于x的边显然不能使图连通,不妨设f(x)表示只选择小于x的边不能使图连通的概率,即答案大于等于x的概率,那么很明显答案就是(期望即答案的带权平均数)。

下面来计算f(x)的表达式,f(x)表示只选择小于x的边不能使图连通的概率,再次由于边权在[0,1]均匀分布且互不相关,f(x)等价于每条边有x的概率出现时,不能使图连通的概率。令g(x)=1-f(x),那么g(x)表示每条边有x的概率出现时,可以使图连通的概率。

现在问题集中在求g(x)的表达式上,我们考虑从原图中选出一个点来,剩余部分是原图的一个导出子图,假设这个子图连通的概率为P。若这个点和这个子图之间有k条边,则此时不连通的概率为P*(1-x)^k,连通的概率为1-P*(1-x)^k。而求子图连通的概率P是一个与原问题相同的子问题,用动态规划求解,把导出子图压缩为一个状态即可。

求解完成后我们会得到一个多项式,直接用牛顿-莱布尼茨公式求解它在[0,1]上的定积分即可。

【代码】

这精度简直狂死乱舞,要用__float128才能卡过去,令人掀桌报警(╯‵□′)╯︵┻━┻

http://paste.ubuntu.com/10749098/

评论

© OI技术宅 | Powered by LOFTER