BZOJ3925 [ZJOI2015] 地震后的幻想乡

Description

一个 $n$ 个结点、 $m$ 条边的无向图，所有边权在 $[0, 1]$ 之间均匀分布（互相独立）；求这个图的最小生成树上的最大边权的期望值。

$n \leqslant 8, m \leqslant \frac{n(n-1)}2$ 。

Solution

显然，题目等价于同时修建这$m$条道路时，首次连通的时间期望值。

我们令$p(x)$为首次连通的时间（设它为随机变量$X$）的概率分布函数，也就是$p(x)=\frac{dP(x)}{dx}$，其中$P(t)=Pr(X\geq t)$，那么根据期望的定义有

$$\begin{aligned}E(X)&=\int_0^1p(x)x\mathrm{d}x\\&=\int_0^1p(x)\int_0^x\mathrm{d}t\,\mathrm{d}x\\&=\int_0^1\int_t^1p(x)\mathrm{d}x\,\mathrm{d}t\\&=\int_0^1P(t)\mathrm{d}t\end{aligned}$$

所以我们只需计算$\int_0^1P(t)dt$即可。

考虑如果$X\geq t$，也就是说图在$t$时刻不连通，那么我们可以枚举结点$1$在$t$时刻的连通块里有哪些点。如果有$S(1 \in S)$这些点，那么首先$S$要连通（概率我们定义为$1-P_S(t)$），其次，$S$里的点和其它点之间的边的$e$都大于$t$（概率为$(1-t)^{T(S, \overline S)}$，其中$\overline S$为$S$的补集，$T(A, B)$表示点集$A,B$之间的边数）；由于这两个事件是独立的，所以总的概率是$(1-t)^{T(S, \overline S)}P_S(t)$。$P_S(t)$也可以类似计算，递推式为：

$$P_S(t)=\sum_{1\in S_0 \subsetneq S}(1-t)^{T(S_0, S - S_0)}\left[1-P_{S_0}(t)\right]\qquad(1\in S)$$

边界条件是$P_{\{1\}}(t)=0$，因为单一的点永远是连通的。

那么有

$$\begin{aligned}\int_0^1P_S(t)\mathrm{d}t&=\sum_{1\in S_0 \subsetneq S}\int_0^1(1-t)^{T(S_0, S - S_0)}\left[1-P_{S_0}(t)\right]\mathrm{d}t\\&=\sum_{1\in S_0 \subsetneq S}\left[\int_0^1(1-t)^{T(S_0, S - S_0)}-(1-t)^{T(S_0, S - S_0)}P_{S_0}(t)\mathrm{d}t\right]\\&=\sum_{1\in S_0 \subsetneq S}\left[\frac{1}{1+T(S_0, S - S_0)}-\int_0^1(1-t)^{T(S_0, S - S_0)}P_{S_0}(t)\mathrm{d}t\right]\end{aligned}$$

同理，

$$\int_0^1(1-t)^kP_S(t)\mathrm{d}t=\sum_{1\in S_0 \subsetneq S}\left[\frac{1}{1+k+T(S_0, S - S_0)}-\int_0^1(1-t)^{k+T(S_0, S - S_0)}P_{S_0}(t)\mathrm{d}x\right]$$

边界条件：$\int_0^1P_{\{1\}}(t)(1-t)^k{\rm d}t=\int_0^10{\rm d}t=0$

而我们要求的就是

$$EX = \int_0^1P(t){\rm d}t =\int_0^1(1-t)^0P_{\{1,2,\dots,n\}}(t){\rm d}t$$

于是关于$S, k$递推即可。按$S$从小到大计算，每次枚举子集之后利用位运算$O(n)$求出$T$，总时间复杂度$O(3^nm)$。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 10;
const int M = 45 + 1;
bool vis[1 << N][M];
int siz[1 << N], link[N];
double f[1 << N][M];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int lim = 1 << n;
  for (int i = 0, x, y; i < m; ++i) {
    scanf("%d%d", &x, &y);
    --x; --y;
    link[x] |= (1 << y);
    link[y] |= (1 << x);
  }
  for (int S = 1; S < lim; ++S) siz[S] = siz[S & (S - 1)] + 1;
  for (int S1 = 3; S1 < lim; ++S1) if (S1 & 1) {
    for (int S2 = (S1 - 1) & S1; S2 != 0; S2 = (S2 - 1) & S1) if (S2 & 1) {
      int T = 0;
      for (int i = 0; i < n; ++i) if ((S1 >> i) & (~S2 >> i) & 1)
        T += siz[link[i] & S2];
      for (int i = 0; i + T <= m; ++i)
        f[S1][i] += 1.0 / (i + T + 1) - f[S2][i + T];
    }
  }
  printf("%.6lf\n", f[lim - 1][0]);
  return 0;
}