洛谷3343 [ZJOI2015]地震后的幻想乡

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]$ ,可以发现一个很奇妙的事情:$\displaystyle f[S][i]+g[S][i]={d[S]\choose i}$ 。

考虑转移。枚举子集 $T$ 并在 $S$ 中随便钦定一个点 $x$ ,那么可以写出 $\displaystyle f[S][i]=\sum_{T\subseteq S,x\in T}\sum_{j=0}^{d[T]}g[T][j]{d[S-T]\choose i-j}$ 。


最后考虑怎么计算答案。

根据之前那个转换的式子,容易写出答案为 $\displaystyle\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)$ 。

这个东西看起来比较麻烦,可以化简得到 $\displaystyle\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;
}
最后修改:2019 年 09 月 27 日 01 : 20 PM

2 条评论

  1. xgzc

    为什么不看_rqy的积分题解啊

    1. M_sea
      @xgzc

      你觉得我看得懂不

发表评论