题解 - Codeforces 1874C Jellyfish and EVA

题意简述

给定一个 $n$ 点 $m$ 边的 DAG，拓扑序为 $1\sim n$（无重边）。一个物体初始位置在点 $1$，目标是去到点 $n$。

每当这个物体不在终点而在点 $u$ 时，会分别选择 $u$ 的出边 $u\to v_1$ 和 $u\to v_2$。若 $v_1=v_2$ 则此物体移动到点 $v_1$，否则原地不动并毁去 $u\to v_1$ 和 $u\to v_2$ 两条边。其中 $v_1$ 总是随机选择，但是可以有策略地选择 $v_2$。

求这个物体成功到达点 $n$ 的最大概率。

$2\le n\le 5000$，$0\le m\le\min(\frac{n(n-1)}{2}, 2\times 10^5)$。

解法

不难想到令 $f_u$ 表示当前在点 $u$ 成功到达点 $n$ 的几率，然后做 DAG 上 dp。转移大概形如 $f_u=\sum a_vf_v$，其中 $a_v$ 表示某个系数。边界是 $f_n=1$。

这个系数似乎没有简单求法。但是对于每个出边数 $k$，都有一个唯一对应的系数序列 $a_k$。要最优化决策，实际上就是把最大的 $a_{k,i}$ 对应最大的 $f_v$，次大的对应次大的，依此类推。上面的递推式大概可以写成 $f_u=\sum_{i=0}^{k-1} a_{k,i}f_{v_i}$，其中将出点按 $f$ 值从大到小排序，$a_k$ 也按从大到小排序（下标从 $0$ 开始）。

我们想要求 $a_{i,j}(0\le j<i)$。

边界，有 $a_{1,0}=1$。$i=0$ 时即没有出路，$a_0$ 和为 $0$。

对于 $i>1$，第一次操作，有 $a_{i,0}=\frac{1}{i}$，即只要求随机选的出点恰好一致。

对于更大的 $j$，由于第一次操作失败才会考虑，这样的情况都化为 $i-2$ 的情景。转移的依据就是第一次操作中随机删的点在 $j$ 之前或之后。

有 $a_{i,j}=a_{i-2,j-2}\times\frac{j-1}{i} + a_{i-2,j-1}\times\frac{i-j-1}{i}$。（编写代码时注意边界）

时间复杂度：预处理 $a$ 的时间是 $O(n^2)$，每组数据对每个点都要做一次出边的排序，所以是 $O(n+m\log n)$。

启示：对于难求的系数，考虑 dp 预处理。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 5005;
const int MXM = 200005;
double prob[MXN][MXN], dp[MXN];
int T, N, M;
int to[MXM], nxt[MXM], head[MXN], egsz;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  prob[1][0] = 1;
  for (int i(2); i != MXN; ++i) {
    prob[i][0] = 1.0 / i;
    for (int j(1); j != i; ++j) {
      if (j - 1 < i - 2) prob[i][j] += prob[i - 2][j - 1] * (i - j - 1) / i;
      if (j >= 2) prob[i][j] += prob[i - 2][j - 2] * (j - 1) / i;
    }
  }
  cin >> T;
  while (T--) {
    cin >> N >> M;
    fill(head, head + N, -1);
    egsz = 0;
    for (int x(0), y(0); M--;)
      cin >> x >> y, --x, --y, to[egsz] = y, nxt[egsz] = head[x],
                               head[x] = egsz++;
    dp[N - 1] = 1;
    for (int i(N - 2); ~i; --i) {
      dp[i] = 0;
      vector<double> vec;
      for (int j(head[i]); ~j; j = nxt[j]) vec.emplace_back(dp[to[j]]);
      sort(vec.begin(), vec.end(), greater<double>());
      for (int j(0); j != vec.size(); ++j)
        dp[i] += vec[j] * prob[vec.size()][j];
    }
    cout << setprecision(10) << fixed << dp[0] << endl;
  }
  return 0;
}