首先转化一下答案：
根据提示，发现其实只需要求出 \(e_i\) 对应的排名 \(rk_i\) 就可以得出其期望值 \(\frac{rk_i}{m + 1}\)
所以只需要求排名的期望，最后答案除上 \(m + 1\) 就行了
不难想到能把期望值拆成 \(\sum_{k = 1} ^ m P(k)\times k\)，可以把期望值拆成对应的概率乘上其权值
发现权值很好求，“加上第 \(k\) 条边使原先不连通的图连通”其权值就为 \(k\)
那只需考虑求“加上第 \(k\) 条边后使原先不连通的图连通”的概率 \(P(k)\) 就可算出答案了
感觉 \(P(k)\) 不好算，因为需要满足一个条件“当有 \(k - 1\) 条边时图不连通”
就考虑对 \(P(k)\) 做个前缀和操作 \(P'(k)\sum_{i = 0}^k P(i)\)，这样 \(P'(k) - P'(k - 1)\) 就可得到 \(P(k)\)
而且发现 \(P'(k)\) 的定义为“用 \(k\) 条边使图连通的概率”，没有了“当有 \(k - 1\) 条边时图不连通”这个条件,那就感觉好做多了
又根据古典概率的求法，只需要算出“用 \(k\) 条边使图连通的方案数”和“选 \(k\) 条边的方案数”就可以算出对应的 \(P'(k)\)
发现“选 \(k\) 条边方案数”好求，即为 \(C_{m}^k\)
所以只需要算出“用 \(k\) 条边使图连通的方案数”\(f_k\) 就行了
图连通，便联想到了并查集
这其实就给了一些解题的提示，这道题也可以类似的通过合并两个小集合得到大集合最终算出 \(f_k\)
具体来说，可以对每个集合 \(s\) 算出“用集合内部的边中的 \(k\) 条使 \(s\) 里的点组成的图连通”的方案数 \(f_{k, s}\)
发现好像也有点难做，考虑正难则反，设 \(g_{k, s}\) 为“用集合内部的边中的 \(k\) 条使 \(s\) 里的点组成的图不连通”的方案数，似乎好求些了
当然由于答案需要 \(f_{k, s}\)，要从 \(g_{k, s}\) 推出 \(f_{k, s}\)
发现对于 \(s\) 里的点组成的图，要么连通，要么不连通，即任意一种情况只属于 \(f_{k, s}\) 或 \(g_{k, s}\)
且能发现设“集合内部的边”的数量为 \(szl_s\)，则“用集合内部的边中的 \(k\) 条”的方案数就是 \(C_{szl_s}^k\)
所以能得到 \(f_{k, s} = C_{szl_s}^k - g_{k, s}\)
考虑求 \(g_{k, s}\)
比较容易想到枚举子集把 \(s\) 分成两个集合 \(t, s-t\)，其”内部可以任意连”，但是“两个集合之间不能有连边“
画几个图会发现这样子会算重，原因出自于“内部可以任意连”，举个例子也可以不连，所以就有了很多完全没有连边的情况
对于这个情况，可以直接定义集合 \(t\) 满足“集合内的点组成的图连通”，而 \(s - t\) 这个集合”随意连边“
感性证明一下：假设现在有 \(t, t'\quad (t\not = t')\)
根据前面的方法，考虑 \(t\) 对于 \(t'\) 多出来的一部分点(反过来一样)对于 \(t\) 一定与 \(t\) 里的点有连边，而对于 \(t'\) 这部分点在 \(s - 't\) 部分，一定与 \(t'\) 里的点没有连边，所以这两个集合绝对不重
其实能发现这个转移还是有重复，因为 \(t\) 是 \(s\) 子集，则 \(s - t\) 肯定也是 \(s\) 子集，两部分都连通的情况算重了
考虑选一个点 \(p\in s\)，要求 \(p\in t\) 时才能转移，因为这样子就能满足 \(p\notin s - t\)，两部分就不会算重了
然后就可以考虑转移了，对于 \(t\) 这个集合，“集合内的点组成的图连通”，显然为 \(f_{i, t}\)，对于 \(t - s\) 这个集合，“任意连边”，因为 \(t\) 已经连了 \(i\) 条边，所以 \(s-t\) 只能连 \(k - i\) 条边，明显是一个组合数 \(C_{szl_{s-t}}^{k-i}\)，因为“两个集合之间不能有连边”，直接乘法原理把两部分乘起来就行了：
\(g_{k, s} = \sum\limits_{t\in s}\sum\limits_{i = 0}^{k} f_{i, t}\times C_{szl{s-t}}^{k - i}\quad (p\in t)\)
根据这个式子其实也能发现一个有趣的东西，就是 \(\text{dp}\) 的顺序是不影响答案的，先枚举 \(k\) 和先枚举 \(s\) 都可以
初始化就比较简单了，若只有一个点，则没有边也是连通的，若有多个点，则没有边一定不连通
\(f_{0, s} = \begin{cases}1& (s = 2^j)\\ 0& (s\not = 2^j)\end{cases}, g_{0, s} = \begin{cases}0& (s = 2^j)\\ 1& (s\not = 2^j)\end{cases}\)
时间复杂度 \(O(3^n m^2)\)
#include<bits/stdc++.h>
using namespace std;
#define int64 long long
#define double64 long double
const int N = 10, M = 45 + 5;
int E[N][N];
int szl[1 << N];
int64 C[M][M];
int64 f[M][1 << N], g[M][1 << N];
double64 Ph[M], P[M];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
x--, y--, E[x][y] = E[y][x] = 1;
}
int lim = (1 << n) - 1;
for (int s = 1; s <= lim; s++) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (((s >> i) & 1) && ((s >> j) & 1) && E[i][j]) {
szl[s]++;
}
}
}
}
// 预处理集合内部边的个数
for (int i = 0; i <= m; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
// 预处理组合数
for (int s = 1; s <= lim; s++) {
f[0][s] = 0, g[0][s] = 1;
}
for (int i = 0; i < n; i++) {
f[0][1 << i] = 1, g[0][1 << i] = 0;
}
// 分只有 1 个点或多个点两种情况预处理
for (int s = 1; s <= lim; s++) {
for (int k = 1; k <= m; k++) {
int mustp;
for (mustp = 0; ! ((s >> mustp) & 1); mustp++);
// 求出“必须包含的”p
for (int t = (s - 1) & s; t; t = (t - 1) & s) {
if ((t >> mustp) & 1) {
// 必须要包含 p
for (int i = 0; i <= k; i++) {
g[k][s] += f[i][t] * C[szl[s ^ t]][k - i];
}
// 转移
}
}
f[k][s] = C[szl[s]][k] - g[k][s];
// 推出 f 的值
}
}
double64 ans = 0.0;
for (int i = 0; i <= m; i++) {
Ph[i] = 1.0 * f[i][lim] / C[m][i];
}
// 整个图其实就是 lim(2 ^ n - 1)
for (int i = 1; i <= m; i++) {
P[i] = Ph[i] - Ph[i - 1];
}
// 由概率前缀和推回初始概率
for (int i = 1; i <= m; i++) {
ans += 1.0 * P[i] * i;
}
// 概率 * 权值
printf("%.6Lf", 1.0 * ans / (m + 1));
// 注意求出来的是排名的期望即 rk 的期望，求出 e 的期望需 / (m + 1)
return 0;
}