难度：NOI/NOI+/CTSC

题目描述

        傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。

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

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

输入格式

        第一行两个数n（n≤10）,m，表示地方的数量和边的数量。其中点从1到n标号。 接下来m行，每行两个数a,b，表示点a和点b之间原来有一条边。 这个图不会有重边和自环。

输出格式

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

输入输出样例

Sample input

5 4
1 2
1 5
4 3
5 3

Sample output

0.800000

题解

        就是求最小生成树最大边权的期望值。
        看到这个提示：对于n个[0,1]之间的随机变量x1,x2,…,xn，第k小的那个的期望值是k/(n+1)。这给我们带来了启发，既然要求期望值，只需要求出这条边的期望排名就行了。
        如果所有边的边权都已经确定了，那么将它们排个序，若当加入第x条边时刚好得到生成树，那么排名就是x。
        如果这个概率能算，那么数学期望显然：

        但是这个概率明显是不好算的，考虑等价的说法。令$P(x)$为排名不小于$X$的概率，那么期望就是：

        其实就是：

        考虑$P(i)$的意义：排名不小于$i$。如果前$i-1$小的边能够让图连通，那么排名是绝对不会不小于$i$的。由于所有边的边权等概率随机，故$P(i)$就是在图上随机选$i-1$条边，图不连通的概率。
        总的方案数是$C_m^{i-1}$，显然只需要求不连通的方案数即可，这个可以用状压$DP$枚举子集去求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;
int n, op[15][15], m, sz[1 << 12];
__int128 C[50][50], dp[1 << 12][150][2];

__int128 DP(int s, int b, int q) {
    if (dp[s][b][q] != -1)return dp[s][b][q];
    if (b > sz[s])return 0;
    if (q)return dp[s][b][q] = C[sz[s]][b] - DP(s, b, 0);
    int now = 1, num = 0;
    dp[s][b][q] = 0;
    while ((now & s) == 0)now <<= 1;
    for (int i = 0; i < (1 << n); i++) {
        if ((i | s) != s || (i & now) == 0 || i == s)continue;
        ++num;
        for (int j = 0; j <= b; j++)dp[s][b][q] += DP(i, j, 1) * (b - j > sz[i ^ s] ? 0 : C[sz[i ^ s]][b - j]);
    }
    if (b == 0)return dp[s][b][q] = num != 0;
    return dp[s][b][q];
}

int main() {
    scanf("%d%d", &n, &m), memset(dp, -1, sizeof(dp));
    for (int i = 1, x, y; i <= m; i++)scanf("%d%d", &x, &y), op[x][y] = 1;
    C[0][0] = C[1][0] = C[1][1] = 1;
    for (int i = 2; i <= 49; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 1; j <= 10; j++) {
            for (int z = 1; z <= 10; z++) {
                if (op[j][z] && ((1 << (j - 1)) & i) && ((1 << (z - 1)) & i))++sz[i];//统计边数
            }
        }
    }
    long double ans = 0;
    for (int i = 0; i < m; i++)ans += (long double) DP((1 << n) - 1, i, 0) / C[m][i];
    printf("%.6Lf", ans / (m + 1));
    return 0;
}