题解

算法分析

本题是一个基于 最小生成树 和 概率期望 的问题，使用 状态压缩动态规划 和 容斥原理 来计算期望值。

问题本质

我们需要计算在 $m$ 条边中选出 $n-1$ 条边构成生成树，并且这些边的修复时间（独立均匀分布在 $[0,1]$）的最大值的期望。

核心思路

1. 利用提示公式：对于 $k$ 个 $[0,1]$ 均匀分布随机变量，第 $i$ 小的期望为 $\frac{i}{k+1}$。因此最大值的期望为 $\frac{k}{k+1}$。

2. 关键转化：如果知道在所有大小为 $n-1$ 的边集中，恰好有 $k$ 个边集能构成生成树，那么总期望为：

   $$E = \sum_{k} \frac{k}{m+1} \times \frac{\text{大小为 }n-1\text{ 且能构成生成树的边集个数}}{\binom{m}{n-1}} $$

   但实际需要更精细的计数。

3. 状态压缩DP：

   • 状态 $S$：表示点集
   • $g[S][i][0/1]$：在点集 $S$ 中，选择 $i$ 条边，且这些边不构成/构成连通图的方案数
   • 使用容斥：连通图数 = 所有图数 - 不连通图数

4. 转移方法：

   • 固定包含最小标号点的连通分量 $T$
   • 用 $g[T][j][1]$（连通）乘以剩余部分 $S\backslash T$ 中任意选 $i-j$ 条边的方案数

算法标签

• 状态压缩动态规划
• 容斥原理
• 图计数
• 概率期望
• 最小生成树

关键代码解析

// 预处理组合数
rep1(i, 0, m) {
    c[i][0] = 1;
    rep1(j, 1, i) c[i][j] = c[i-1][j-1] + c[i-1][j];
}

// 计算每个点集内的边数
rep1(i, 1, m) {
    auto [u, v] = e[i];
    rep1(S, 1, lmt) if ((S>>u-1&1) && (S>>v-1&1))
        ++ecnt[S];
}

// 状态压缩DP
rep1(S, 0, lmt) rep1(i, 0, ecnt[S]) {
    g[S][i][0] = 0;
    
    // 枚举包含最小点的连通分量T
    for(int T = S&(S-1); T; T = S&(T-1)) {
        if(T & (S&-S)) {  // 包含最小点
            rep1(j, 0, ecnt[T]) {
                // 容斥转移
                g[S][i][0] += g[T][j][1] * c[ecnt[S^T]][i-j];
            }
        }
    }
    
    g[S][i][1] = c[ecnt[S]][i] - g[S][i][0];
}

// 计算最终期望
ld ans = 0;
rep1(i, 0, m-1) ans += 1.0 * g[lmt][i][0] / c[m][i];
ans /= m + 1;

时间复杂度

• 状态数：$O(2^n)$
• 每个状态枚举子集：$O(3^n)$
• 边数枚举：$O(m)$
• 总体复杂度：$O(3^n \cdot m^2)$，在 $n \leq 10$ 时可接受

空间复杂度

• $O(2^n \cdot m)$，用于存储 DP 状态

算法正确性

1. 通过容斥准确计算了每个点集的连通子图数量
2. 利用概率论公式将连通图计数转化为期望计算
3. 状态压缩确保所有子集情况都被考虑

总结

本题结合了图论、组合数学和概率论，通过状态压缩DP和容斥原理解决了生成树期望问题。关键在于将概率期望转化为图计数问题，并使用DP高效计算所有可能的连通情况。