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

· · 题解

嗯...既然这题没有题解那我就来写一个吧！

显然，题目等价于同时修建这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)。

PS：搞了一晚上终于抢下rk1了。

#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;
}