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

· · 题解

先膜拜积分大佬！

就着这道题谈一下我做概率期望题的感想吧。

这之中离不开的就是方案数+概率+期望

大家都知道

\text{概率}=\text{方案数}/\text{总方案数} \text{期望}=\text{概率}*\text{对应权}

如果一道题加模数的话，三个量可以不掉精度地转化，以方便我们的分析。

(比如这道题)

回到本题的平民做法，我们知道要求的是最小生成树上边的最大值的期望。

这东西一看就很不好求，而且边的权都不是离散的，而是[0,1]以内的随机实数，这就很不方便处理。

题目很良心，有一个提示：

对于n个[0,1]之间的随机变量x1,x2,...,xn，第k小的那个的期望值是k/(n+1)

这让我们想到把期望转化成排名的期望，这样子就能化连续为离散（一般来讲，这可以使问题变简单，在P3600里面也有这样的细节）。

现在主要的复杂点就在于最小生成树,这是个很复杂的东西，我们想方设法挖掘本质，将它变简单。

假设你知道了边的排名，然后在跑克鲁斯卡尔。

你会一条一条地加边，然后判断是否生成了树。

答案就是最后加入的那一条边的排名。

那么我们就有了第一个算法：

枚举边的排名，然后跑克鲁斯卡尔。

得到排名的期望，再除以(m+1)得到答案。

复杂度O(m*m!)据说分数可观。

我们考虑“生成了树”的本质是什么，在克鲁斯卡尔中，就是把n个点都联通了起来。

一个最小生成树内最大的边排名为x的概率=用k条边恰好联通整个图的概率（这个很好理解吧）

根据期望的定义，排名的期望=\sum P(x)*x

其中P(x)是用k条边恰好联通整个图的概率。

恰好的意思是，没有第k条边的时候，不连通，加一条边就联通了。

这个限制令人头疼，我们把它前缀和一下（P3600里面也有类似套路）

得到P'(x)=\sum\limits_{i=0}^nP(x)

根据人类智慧P(x)'=一条边联通全图的概率+二条边联通全图的概率+...=用排名前k的边联通整个图的概率。

（仔细体味P(x)和P'(x)的不同）。

然后因为前缀和,P(x)'-P'(x-1)=P(x)

我们只要想办法弄出P'(x)就好了。

至此，问题已经变成了图的联通性问题（边的选取问题）。

那么问题来了，这玩意怎么求？

如果一道题加模数的话，三个量可以不掉精度地转化，以方便我们的分析。

这道题没加模数，不代表我们不能转化，我们考虑转化成方案数。

方案数会不会爆long long，因为最多只有45条边，最多就是C_{45}^{23}=4116715363800,稳得一批。

这里我们采用dp求方案数。

设f[i][s]表示使用i条边联通了s这个集合的方案数。

想了想发现不可做。

于是采用正难则反，这g[i][s]表示使用i条边没有联通s这个集合的方案数。

我们设c[x][y]表示C_x^y(注意谁在下面),设siz[s]表示点集s内部有多少边。

一个很好理解的东西c[siz[s]][i]=g[i][s]+f[i][s]，因为g和f组成了所有选取的方法。

我们考虑如何转移出g[i][s]：

我自然地想到了枚举子集，把s区分成了两个真子集s1,s2(即不能枚举空集)。

（如果没听说过枚举子集的话建议上网查一下，或者去做P3959）

那么，必须令这s不连通，那好办，直接令这s1,s2之间没有边。

那么s1,s2内部就可以随便连。

这样肯定是不会算漏，但会重复。

第一次分割
1 #  2
  # 
###  3
根据任意连边，所有点之间都不连边的方案适合这个分割线

第二次分割
1 #  2
  ####
    3
根据任意连边，所有点之间都不连边的方案也适合这个分割线

很明显存在重复计算

之所以会存在重复计算，是因为分割线可能会重复穿过“随便连”的部分。

我们dp出了f数组，现在可以拿来用，我们规定s1内必须联通，s2内可以随便。

这样子，分割线就不会再次穿过s1（因为其内部联通）

现在还有一个问题，如果s1与s2调换，还是会存在重复算的情况(必须联通∈随便连)

所以当我们枚举过某个s1时，就不能再次枚举它的补集作为s1。

这里有个非常脑洞的操作,随便钦点一个s内的点p，令s1必须包含p，这样子，枚举过的s1的补集必然不包含p，也就被排除在外了。

理解了这些(建议结合其他题解理解这个，真的不好懂)就好办了，下面是dp的代码与详细注释：

long long f[50][1200],g[50][1200],c[50][50];
//f:联通; g:不连通; c:组合数; 
int siz[1200];
//siz:某点集内边的数量;
bool e[12][12];
//e:邻接矩阵;

  for (int s=0;s<=limit;s++)g[0][s]=1;
  for (int i=0;i<n;i++)
   {f[0][1<<i]=1;g[0][1<<i]=0;}
  //根据“一个点自身是联通的”来初始化
  for (int s=0;s<=limit;s++)
   for (int i=0;i<n;i++)
    for (int j=i+1;j<n;j++)
     if (e[i][j]&&((1<<i)&s)&&((1<<j)&s))
      siz[s]++;
  //求解siz
  for (int i=0;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 i=1;i<=m;i++)
   for (int s=1;s<=limit;s++){
     int p=0;
     for (;((1<<p)&s)==0;p++);
    //寻找一个s内的点(s必然不为空集)
     for (int k=(s-1)&s;k;k=(k-1)&s)
      if ((1<<p)&k){
      //这里还要枚举分给两个子集各多少条边
       for (int j=0;j<=i;j++)
        g[i][s]+=f[j][k]*c[siz[s^k]][i-j];
        //如上文，一部分随便选，一部分必须联通
      }
     f[i][s]=c[siz[s]][i]-g[i][s];
     //根据c[siz[s]][i]=g[i][s]+f[i][s]求出f[i][s]
   }

至此，dp的部分就讲完了，我们回到概率P'(x)上来。

就是$P(x)'=\dfrac{f[x][\text{全集}]}{c[m]][x]}

代码

double p[50],p2[50];

  double ans=0;
  for (int i=0;i<=m;i++)
    p2[i]=(double)f[i][limit]/(double)c[m][i];
  //计算p'
  for (int i=0;i<=m;i++)p[i]=p2[i]-p2[i-1];
  //计算p
  for (int i=0;i<=m;i++)ans+=p[i]*i;
  //计算排名的期望
  printf("%.6lf",ans/(m+1));
  //得到最大边的期望

AC记录