Luogu

LOJ

分析

首先看到题目里的提示：

对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\cdots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 。

考虑一个暴力做法：枚举边权的相对大小，然后 Kruskal 求最小生成树并用这个提示算答案。​

进一步考虑这样的一个做法：钦定一个边集 $S$ 作为前 $|S|$ 小的边，如果这个边集在加入第 $|S|$ 条边时恰好连通，那么它的贡献就是 $\frac{|S|}{m+1}$ 。

如果我们知道每个边集对应的方案数，那么即可求出答案。

恰好连通这个条件很烦，考虑差分，转化成加之前不连通-加之后不连通。

考虑 DP 求解方案数。设 $f_{S, i}$ 表示选了 $i$ 条边，点集 $S$ 不连通的方案数，$g_{S, i}$ 表示选了 $i$ 条边，点集 $S$ 连通的方案数。

设点集 $S$ 在图中的边数为 $d_S$，那么显然有
$$
f_{S, i}+g_{S, i}={d[S]\choose i}
$$

考虑转移。枚举子集 $T$ 并在 $S$ 中随便钦定一个点 $x$，那么可以写出
$$
f_{S, i}=\sum_{T\subseteq S,x\in T}\sum_{j=0}^{d_T}g_{T, j}{d_{S - T}\choose i-j}
$$

最后考虑怎么计算答案。根据之前的差分，可以写出答案为
$$
\sum_{i=1}^{m+1}\frac{i}{m+1}\times\left(\frac{f_{U, i - 1}}{d_U\choose i-1}-\frac{f_{U, i}}{d_U\choose i}\right)
$$

化简得到
$$
\frac{1}{m+1}\sum_{i=1}^m\frac{f_{U, i}}{d_U\choose i}
$$

具体实现和细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+10,M=45+10,L=1<<10;

int n,m,lim;
int e[L],d[L];
double C[M][M],f[L][M],g[L][M];

int main() {
    n=read(),m=read(),lim=1<<n;

    for (re int i=C[0][0]=1;i<=m;++i)
        for (re int j=C[i][0]=1;j<=i;++j)
            C[i][j]=C[i-1][j]+C[i-1][j-1];

    for (re int i=1;i<=m;++i) {
        int u=read()-1,v=read()-1;
        ++e[(1<<u)|(1<<v)];
    }
    for (re int i=1;i<lim;++i)
        for (re int j=i;j;j=(j-1)&i)
            d[i]+=e[j];

    for (re int S=1;S<lim;++S)
        for (re int i=0;i<=d[S];++i) {
            for (re int T=(S-1)&S;T;T=(T-1)&S) {
                if ((T&(S&-S))==0) continue;
                for (re int j=0;j<=min(i,d[T]);++j)
                    f[S][i]+=g[T][j]*C[d[S-T]][i-j];
            }
            g[S][i]=C[d[S]][i]-f[S][i];
        }

    double ans=0;
    for (re int i=0;i<=m;++i) ans+=f[lim-1][i]/C[m][i];
    printf("%.6lf\n",ans/(m+1));
    return 0;
}