over 2 years ago

前言

好神的题目啊。。。话说陈老师这么喜欢出自己讲课的题目啊。。。

题意

(我个傻逼最开始没看懂题目)就是给出个点,条边的无向图,每条边的权值在之间等概率分布,问最小生成树的最大边的期望值。

分析

首先我们考虑两条边权相同的概率为,因此可以认为边权两两不同。
考虑最小生成树的最大边权为(设概率为),那么很显然此时如果只取边权的边,整个图是不联通的。
因此我们的问题变成了:对于图中边权的边集无法使图联通的概率。
其实也就是每条边有的概率被选,然后整个图不联通的概率。
假设已经确定,我们设表示对于某一个点集不联通的概率,类似设表示联通的概率。
具体怎么求呢,其实我们可以类似"无向连通图计数"那道题的方法,选一个

其实就是枚举与某一个点联通的极大点集,表示之间的边数。
那么其实就是一个关于的多项式,求出这个多项式,我们就可以对于任意的来求出了。
再想一想,我们发现只是求出了的边不能联通的概率,这其实也就是最大边权的概率。
为无限小,那么总期望值:

我们不是已经求出了这个多项式吗?所以直接牛顿莱布尼茨公式即可。
据说卡精度,反正__float128可以过。。。
bzoj3925.cpp
(好像缩进有点鬼畜)

← bzoj4037:[HAOI2015]Str BZOJ4197:[Noi2015]寿司晚宴 →
 
comments powered by Disqus