0%

「ZJOI2015」地震后的幻想乡

发表于 更新于 阅读次数： Valine：

给定一张无向图，边权在\([0,1]\)之间随机均匀分布，求这张图的最小生成树边权最大值的期望。

\(1\leqslant n\leqslant 10\)，\(1\leqslant m\leqslant \frac{n(n-1)}{2}\)（分别是点数与边数）

提示：对于\(n\)个\([0,1]\)之间的随机变量\(x1\),\(x2\),...,\(xn\)，第\(k\)小的那个的期望值是\(\frac{k}{n+1}\)。

如果我们按照边权从小到大加入边，那么最下生成树边权的最大值也就是加入某一条边使得图恰好联通的那条边的权值。于是我们只需计算这张图是从小到大加了第\(i\)条边后恰好联通的概率，记为\(P[i]\)，则 \[ ans=\sum\limits_{i=1}^{m}P[i]E[i] \] 其中\(E[i]\)是这条边的边权期望，由提示我们知道\(E[i]=\frac{i}{m+1}\)，那么 \[ ans=\frac{1}{m+1}\sum\limits_{i=1}^m iP[i]\\ =\frac{1}{m+1}\sum\limits_{i=1}^m\sum\limits_{j=i}^mP[j] \] 我们设\(p[i]=\sum\limits_{j=i}^mP[j]\)那么\(ans=\frac{1}{m+1}\sum\limits_{i=1}^m p[i]\)，而\(p[i]\)的意义是加入至少\(i\)条边才联通的概率，这显然比\(P\) 要好计算！

我们考虑如何计算\(p\)，不难发现这等价于加了\(i-1\)条边还没有联通的概率，可以用不连通方案数除以总方案数来计算概率。于是我们成功的把一个期望问题转化为了计数问题！

考虑状压计算方案，设\(f[i][s]\)和\(g[i][s]\)为当前点集为\(s\)，内部连了\(i\)条边，联通/不连通的方案数，那么有 \[ f[i][s]+g[i][s]=\binom{size[s]}{i}\\ f[i][s]=\sum\limits_{j=0}^{i-1}\sum\limits_{t\subsetneqq s且r\in t}g[j][t]*\binom{size[s-t]}{i-j} \] 第一条，不连通+联通=总方案数，其中\(size[s]\)为子图\(s\)中的边数

第二条，\(r\)是\(s\)中的第一个点（其实可以是任何一个但是在枚举\(j\)和\(t\)中不能变），这样的话通过枚举这个点所在的连通块大小，可以不重不漏计算出所有不连通图的数量（连通图计数貌似有很多类似的trick，可惜我并没做过）

最后答案式子就不列了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
int ss[46],tt[46],cnt[1+1<<10];
ll f[1+1<<10][46],g[1+1<<10][46],c[46][46];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&ss[i],&tt[i]),ss[i]--,tt[i]--;
    for(int i=1;i<(1<<n);i++)
        for(int j=1;j<=m;j++)
            if((i&(1<<ss[j]))&&(i&(1<<tt[j])))cnt[i]++;
    c[0][0]=1;
    for(int i=1;i<=45;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    for(int s=1;s<(1<<n);s++)
    {
        if(s==(s&(-s))){g[s][0]=1;continue;}
        int lowbit=(s&(-s));
        for(int t=s&(s-1);t;t=s&(t-1))
        {
            if(!(t&lowbit))continue;
            for(int i=0;i<=cnt[t];i++)
                for(int j=0;j<=cnt[s^t];j++)
                    f[s][i+j]+=g[t][i]*c[cnt[s^t]][j];
        }
        for(int i=0;i<=cnt[s];i++)g[s][i]=c[cnt[s]][i]-f[s][i];
    }
    long double ans=0;
    for(int i=0;i<=m;i++)ans+=1.0*f[(1<<n)-1][i]/c[cnt[(1<<n)-1]][i];
    printf("%.6Lf",ans/(m+1.0));
    return 0;
}

代码里更新方式和上面长得不太一样，但实际上是一个东西。复杂度为\(O(3^nm)\)