题解：P3343 [ZJOI2015] 地震后的幻想乡

题意：给出一个图，无重边自环，边权为 \([0,1]\) 内的随机数，问最小生成树最大边权的期望。

做法：

注意到题目中有一个 hint：\(m\) 个随机变量的 \(k\) 小值期望是 \(\frac{k}{m+1}\)，考虑怎么使用。

考虑暴力，因为边权是连续而不是离散的，不能直接枚举，所以一个更好的想法是我们枚举边的排名，这样同样是可以做 kruskal 的，然后再利用这个 hint 直接算出答案。

考虑到答案其实是对 \(\frac{k}{m+1}\) 乘上 \(k\) 这条边连通的概率，所以转化一下，变成对 \(\ge k,k\in [0,m-1]\) 的时候仍然不连通的概率。

那么很自然地枚举 \(1\) 所在的集合 \(S\)，设补集为 \(S'\)，那么要求 \(S\) 内部连通，\(S'\) 随意。但是我们不好计算直接连通的方案数。

所以我们考虑 dp，\(f_{s,i},g_{s,i}\) 分别代表 \(s\) 这个集合用了 \(i\) 条边，不连通/连通的方案数。考虑如何转移。

既然我们要求 \(g\)，那么肯定考虑 \(g\) 的转移，但是没啥好的方法。我们注意到 \(f_{s,i}+g_{s,i}=\binom{|E(s)|}{i}\)，所以可以转为求 \(f\)。

那么 \(f\) 就类似于我们求答案的时候的思路，直接找 lowbit 所在的集合 \(S\)，设补集为 \(S'\)，枚举我分给 \(S\) 共 \(x\) 条边，那么贡献是：

\[g_{S,x}\binom{|E(S')|}{i-x} \]

解释一下，前者是 \(S\) 连通的方案数，后者是因为 \(S'\) 不能和 \(S\) 中有连边，所以只用管 \(S'\) 内部的，而 \(S'\) 内部不要求连通，随意选就可以。

按上述柿子计算即可，复杂度 \(O(3^nm^2)\)。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x & (-x))
const int maxn = 15, N = (1 << 11) + 5;
int n, m, d[N];
double f[N][maxn * maxn], g[N][maxn * maxn], C[maxn * maxn][maxn * maxn];
signed main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y; cin >> x >> y;int nw = ((1 << x - 1) | (1 << y - 1));for (int s = 0; s < (1 << n); s++)if((s & nw) == nw)d[s]++;}C[0][0] = 1;for (int i = 1; i <= m; i++) {C[i][0] = 1;for (int j = 1; j <= m; j++)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);}for (int s = 0; s < (1 << n); s++) {for (int j = 0; j <= d[s]; j++) {int lb = lowbit(s);for (int t = (s - 1) & s; t; t = (t - 1) & s) {if(!(t & lb))continue;for (int k = 0; k <= min(j, d[t]); k++)f[s][j] = (f[s][j] + g[t][k] * C[d[s ^ t]][j - k]);}g[s][j] = C[d[s]][j] - f[s][j];//	cout << s << " " << j << " " << g[s][j] << endl;}}double ans = 0;for (int i = 0; i <= m; i++)ans += f[(1 << n) - 1][i] / C[m][i];cout << fixed << setprecision(6) << ans / (m + 1) << endl;return 0;
}