题意
给定一个有向无环图，对于任意一条边 \((u_i, v_i)\)，有 \(u_i < v_i\)。
定义一次从节点 \(u\) 开始的移动为如下过程：
-
\(\tt{Alice}\) 选择从 \(u\) 出发的且未被删除的一条边。
-
\(\tt{Bob}\) 在从 \(u\) 出发的且未被删除的边中等概率随机选择一条。
-
若两人选择的边相同，则向这条边移动，否则继续选择。
如果不存在从当前节点 \(u\) 出发且未被删除的边，那么定义此次移动是失败的。
若 \(\tt{Alice}\) 采取最优策略，求他们实现移动 \(1 \rightarrow n\) 的概率。
（\(1 \le n \le 5000\)）。
题解
定义 \(f_u\) 代表从节点 \(u\) 实现移动 \(u \rightarrow n\) 的最大化概率，那么可见答案为 \(f_1\)，由于特殊的边的限制，从 \(1\) 到 \(n\) 显然是一个合法的拓扑序，逆序遍历转移一定合法，下面考虑如何转移。
设 \(d = \operatorname{degree}_u\)，定义从 \(u\) 出发的所有边的终点依次为 \(v_1, v_2, \cdots, v_d\)，将其按 \(f_v\) 为关键字降序排列得到序列 \(v\)。
可以发现，若 \(\tt{Alice}\) 选择边的方案钦定，那么可以得出移动到每个终点的概率，设有长度为 \(d\) 的序列 \(p\)，其中 \(p_1\) 表示移动到 \(v_1\) 的概率，那么我们有
那么采取最优操作的实质即为通过改变操作序列来最大化上述和式的值。
由于在任意一次选择中，每个点被 \(\tt{Bob}\) 选择的概率相等，那么显然选择 \(f\) 值最大的终点可以获得更大的概率。这样我们就得到了最优操作的策略：选择 \(f\) 值最大的终点。
设 \(g_i\) 表示在有 \(i\) 个点的情况下的最优 \(p\) 序列，那么有
对于 \(i > 2\) 的情况，根据上述策略，我们可以发现 \(\tt{Alice}\) 第一次选择的点一定为 \(v_1\)，那么我们有
对于 \(j > 1\)，那么第一次显然不可能成功移动到 \(v_j\)。若最终成功移动到了 \(v_j\)，那么有第一次移动一定失败且 \(v_j\) 没有被删除。那么此时我们可以从 \(i - 2\) 个节点的状态转移答案。考虑通过枚举除 \(v_1\) 外被删除的节点来实现转移，设另外一个被删除的节点为 \(v_k\)，那么有
-
若 \(j < k\)，那么 \(v_j\) 从当前的第 \(j\) 优节点转化为 第 \(j - 1\) 优节点，有转移 \(g_{i, j} \leftarrow g_{i - 2, j - 1} (j < k)\)。
-
若 \(k < j\)，那么 \(v_j\) 从当前的第 \(j\) 优节点转化为 第 \(j - 2\) 优节点，有转移 \(g_{i, j} \leftarrow g_{i - 2, j - 2} (k < j)\)。
发现具体的转移与 \(k\) 无关，通过计算 \(j < k\) 的概率和 \(k > j\) 的概率即可完成转移，有转移式
预处理出 \(g\) 数组即可实现转移，复杂度 \(\mathcal{O}(n^2)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef long double realType;
typedef std::vector<realType> RealVector;
typedef std::vector<RealVector> RealMatrix;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N, M;
std::cin >> N >> M;
RealMatrix G(N + 1, RealVector(N + 1, 0));
for (valueType i = 1; i <= N; ++i) {
G[i][1] = (realType) 1 / i;
for (valueType j = 2; j <= i && i - 2 > 0; ++j)
G[i][j] = G[i - 2][j - 2] * (j - 2) / i + G[i - 2][j - 1] * (i - j) / i;
}
ValueMatrix Graph(N + 1);
for (valueType i = 0; i < M; ++i) {
valueType u, v;
std::cin >> u >> v;
Graph[u].push_back(v);
}
RealVector F(N + 1, 0);
F[N] = 1;
for (valueType i = N - 1; i >= 1; --i) {
auto const degree = (valueType) Graph[i].size();
RealVector to;
to.reserve(degree);
for (auto const &iter: Graph[i])
to.push_back(F[iter]);
std::sort(to.begin(), to.end(), std::greater<>());
F[i] = 0;
for (valueType j = 1; j <= degree; ++j)
F[i] += G[degree][j] * to[j - 1];
}
std::cout << std::fixed << std::setprecision(10) << F[1] << std::endl;
}
return 0;
}