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

想了半天，打开洛谷题解一看，最高票是_rqy的，一堆密密麻麻的积分差点把我吓跑。

据说有三种解法，然而我只学会了一种最辣鸡的凡人解法。

upt:更正了一些错误..

题意：给一个无向图G，边权为[0,1]间的实数，求这个图的最小生成树的最大边权期望。

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

考虑使用这个提示来帮助解题。

首先有一个暴力做法，枚举边权的相对大小，然后做最小生成树，kruskal得到一棵树时拿提示算一下

这个想法启发我们钦定一个边集S作为前|S|小，如果这个边集加入第|S|小这条边时恰好使图联通，我们就可以算它的贡献是\frac{|S|}{m+1}，如果我们还能算出它的方案并除上总方案，我们就可以得到它的概率，所以考虑去统计这个方案。

恰好联通这个条件并不好统计，我们转换一下，可以变成

恰好联通方案=加之前不连通方案-加之后不连通方案

然后比较自然的可以考虑压一个子集去做dp

令f_{S,i},g_{S,i}分别表示点集为S，用了i条边，且点集不联通/连通的方案数，设d_S为点集s在图G中的边数

显然有

g_{S,i}+f_{S,i}=\binom{d_S}{i}

考虑f的递推，我们枚举s的子集，并且钦定某个点k一定在子集里，有转移

f_{S,i}=\sum_{k\in T\subset S}\sum_{j=0}^{d_T}g_{T,j}\binom{d_{S-T}}{i-j}

然后最后考虑如何统计答案，设U为全集，按照之前说的，答案为

\sum_{k=1}^{m+1}\frac{k}{m+1}\times (\frac{f_{U,k-1}}{\binom{d_u}{k-1}}-\frac{f_{U,k}}{\binom{d_u}{k}})

化简一下

\frac{1}{m+1}\sum_{k=1}^m\frac{f_{U,k}}{\binom{d_U}{k}}

Code:

#include <cstdio>
#include <cctype>
#include <algorithm>
using std::min;
template <class T>
void read(T &x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
double C[51][51],f[1<<10][51],g[1<<10][51];
int yuu[1<<10],dew[1<<10],n,m;
int main()
{
    read(n),read(m);
    for(int u,v,i=1;i<=m;i++)
    {
        read(u),read(v);
        ++dew[(1<<u-1)|(1<<v-1)];
    }
    for(int s=1;s<1<<n;s++)
        for(int t=s;t;t=t-1&s)
            yuu[s]+=dew[t];
    C[0][0]=1;
    for(int i=1;i<=m;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++)
    {
        for(int i=0;i<=yuu[s];i++)
        {
            for(int t=s-1&s;t;t=t-1&s)
                if(t&(s&-s))
                    for(int j=0;j<=min(i,yuu[t]);j++)
                        f[s][i]+=g[t][j]*C[yuu[s^t]][i-j];
            g[s][i]=C[yuu[s]][i]-f[s][i];
        }
    }
    double ans=0;
    for(int i=0;i<=m;i++) ans+=f[(1<<n)-1][i]/C[m][i];
    ans/=m+1.0;
    printf("%.6f\n",ans);
    return 0;
}