P3343 [ZJOI2015] 地震后的幻想乡

题目描述

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

这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 $n$ 个地方，那么最快的方法当然是修复 $n - 1$ 条道路将这 $n$ 个地方都连接起来。幻想乡这 $n$ 个地方本来是连通的，一共有 $m$ 条边。现在这 $m$ 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 $i$ 条边所需要的时间为 $e_{i}$ 。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 $e_{i}$ 会是一个 $0$ 到 $1$ 之间均匀分布的随机实数。并且所有 $e_{i}$ 都是完全独立的。

现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 $n - 1$ 条边，同时开始修复，那么修复完成的时间就是这 $n - 1$ 条边的 $e_{i}$ 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 $e_{i}$ 的值，然后再选择完成时间最小的方案。幽香在走之前，她想知道修复完成的时间的期望是多少呢？

输入格式

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

接下来 $m$ 行，每行两个数 $a, b$ ，表示点 $a$ 和点 $b$ 之间原来有一条边。这个图不会有重边和自环。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

1	`0.800000`

说明/提示

样例解释

对于第一个样例，由于只有四条边，幽香显然只能选择这四条，那么答案就是四条边的 $e_{i}$ 中最大的数的期望，由提示中的内容，可知答案为 $0.8$ 。

提示

（以下内容与题意无关，对于解题也不是必要的。）

对于 $n$ 个 $[0, 1]$ 之间的随机变量 $x_{1}, x_{2}, . . ., x_{n}$ ，第 $k$ 小的那个的期望值是 $k / (n + 1)$ 。

数据范围：

对于所有数据： $n \leq 10, m \leq n (n - 1) / 2, n, m \geq 1$ 。

对于 $15 %$ 的数据： $n \leq 3$ 。

另有 $15 %$ 的数据： $n \leq 10, m = n$ 。

另有 $10 %$ 的数据： $n \leq 10, m = n (n - 1) / 2$ 。

另有 $20 %$ 的数据： $n \leq 5$ 。

另有 $20 %$ 的数据： $n \leq 8$ 。

题解

题意：给一个无向图 $G$ ，边权为 $[0, 1]$ 间的实数，求这个图的最小生成树的最大边权期望。

暴力算法：枚举边权的相对大小排序，对每个排序 Kruskal 得到 MST 时计算期望。

暴力算法启发我们钦定一个边集 $S$ 作为边权最小的 $| S |$ 条，如果这个边集加入第 $| S |$ 小这条边时恰好使图联通。由题中提示可知， $S$ 构成的 MST 的最大边权期望是 $\frac{| S |}{m + 1}$ 。我们还需要算出 $S$ 对应的方案数并除上总方案数，我们就可以得到它的概率。

接下来是状压 DP。令 $f (S, i), g (S, i)$ 分别表示点集为 $S$ ，用了 $i$ 条边，且点集不连通/连通的方案数。令 $d_{S}$ 表示点集 $S$ 内部在图 $G$ 中的边数。

显然有

g (S, i) + f (S, i) = (\binom{d_{S}}{i})

考虑 $f (S, i)$ 的递推。我们钦定一个点 $k$ ，枚举 $k$ 所在的连通块图 $T$ 。则 $S$ 不连通当且仅当 $T$ 和 $S ∖ T$ 不连通。于是有如下转移：

f (S, i) = \sum_{k \in T, T \subset S} \sum_{j = 0}^{d_{T}} g (T, j) (\binom{d_{S ∖ T}}{i - j})

我们将“恰好联通方案数”转换成“加之前不连通方案数 - 加之后不连通方案数”。令 $V$ 表示所有节点的集合，答案为

\sum_{k = 1}^{m + 1} \frac{k}{m + 1} \times (\frac{f (V, k - 1)}{(\binom{d_{V}}{k - 1})} - \frac{f (V, k)}{(\binom{d_{V}}{k})})