传送门

题意：

给定一个n点m边的无向图，没有重边和自环，每条边的权值为 [0,1] [ 0 , 1 ] 之间的随机变量，求最小生成树中最大边的期望权值。

n≤10,m≤n(n−1)2 n ≤ 10 , m ≤ n ( n − 1 ) 2

Solution:

题意其实可以转化为选前k小的那些边使图恰好联通，求k的期望

答案即为 k(m+1) k ( m + 1 )

那么我们只要分别求出选1-m条边使图恰好联通的概率，再把他们加起来即可得到k

概率可以通过合法方案除总方案数来得出：

num[S] n u m [ S ] 表示两个端点都在S内的边的个数

f[S][i] f [ S ] [ i ] 表示只考虑S这个集合的点，在其中选了i条边，这些点不连通的方案数

g[S][i] g [ S ] [ i ] 表示只考虑S这个集合的点，在其中选了i条边，这些点连通的方案数

那么 f[S][i]+g[S][i]=Cinum[S] f [ S ] [ i ] + g [ S ] [ i ] = C n u m [ S ] i

那么应该如何转移才能使得不会算重呢？这里有一个惯用的套路：每次固定一个点集中的点，枚举包含这个点的联通块的大小

依据上面的条件我们可以得到：

f[S][i+j]=∑T⊂Sg[T][i]∗Cjnum[S−T] f [ S ] [ i + j ] = ∑ T ⊂ S g [ T ] [ i ] ∗ C n u m [ S − T ] j

注意所有的T都必须要包含我们所固定的点，注意这是真子集

设all是全集

最后的答案就是 ∑mi=0f[all][i]Cim∗(m+1) ∑ i = 0 m f [ a l l ] [ i ] C m i ∗ ( m + 1 )

这样我们每次转移是枚举子集，复杂度 O(3nm) O ( 3 n m )

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int num[1<<10],x[110],y[110];
int n,m,E[110][110];
bool vis[1<<10];
long long f[1<<10][100],g[1<<10][100],C[110][110];
int main()
{
    scanf("%d%d",&n,&m);
    C[0][0]=1;
    for (int i=1;i<=45;i++)
    {
        C[0][i]=1;
        for (int j=1;j<=i;j++)
            C[j][i]=C[j-1][i-1]+C[j][i-1];
    }
    for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
    for (int i=0;i<(1<<n);i++)
        for (int j=1;j<=m;j++)
            if (((i>>x[j]-1)&1)&&((i>>y[j]-1)&1)) num[i]++;
    //for (int i=1;i<(1<<n);i++) f[i][0]=1;
    for (int i=0;i<n;i++) vis[1<<i]=1,g[1<<i][0]=1;
    for (int S=1;S<(1<<n);S++)
    {
        if (vis[S]==1) continue;
        int lowbit=(S&(-S));
        for (int k=(S-1)&S;k;k=(k-1)&S)
            if (k&lowbit)
            {
                for (int i=0;i<=num[S];i++)
                    for (int j=0;j<=num[S-k];j++)
                        f[S][i+j]+=g[k][i]*C[j][num[S-k]];
            }
        for (int i=0;i<=num[S];i++)
            g[S][i]=C[i][num[S]]-f[S][i];
        }
    double ans=0;
// for (int i=0;i<(1<<n);i++){
   
// for (int j=0;j<=m;j++)
// cout<<f[i][j]<<" ";cout<<num[i]<<":"<<i<<endl;}
    for (int i=0;i<=m;i++) ans+=1.0*f[(1<<n)-1][i]/C[i][m];
    printf("%.6f",ans/(m+1));
}