P6030

· · 题解

UPD On 2024/07/23：被 Hack 了，更新了提交记录，同时增加了对 Hack 数据的说明。

考虑这是一道随机游走的板子题，于是一定有 O(n^3) 的朴素高斯消元解法。但是过不了。

题面中专门给了你这个加粗的字，然后一想，设强连通分量大小为 x，那么我们有一个 O(x^3\times\frac{n}{x}) 的复杂度，代表着对于每一个强连通分量进行高斯消元的做法复杂度正确。

首先判断特殊情况。如果我们 tarjan 缩点之后发现有一个非只有经过终点才可达且非终点所在的强连通分量出度为 0，那么进入这个强连通分量代表着一直到不了终点。根据期望的线性性，可以知道这个强连通分量对答案的贡献是 +\infty 乘上一个常数。此时答案就是 +\infty。判断粗体部分就从 s 开始进行不经过 t 点的 DFS 就行。

然后拓扑排序，按拓扑序逆序求解每一个强连通分量。重新审视朴素求解随机游走的式子：

f_{i}=[i\not = t]\left(1+\frac{1}{deg_i}\sum_{(i,j)\in E}f_j\right)

发现对于缩点之后的结果，各个强连通分量之间的所有关系都是固定的，所以无后效性，可以直接转移。其他仍然用高斯消元求解即可。

判断 INF 的话要么就是终点不可达，要么就是存在上面说的情况。

实现起来有点史。

AC 记录