[省选联考 2021] 图函数 题解

· · 题解

首先考虑分析 f(u, G)，可以观察出一些性质 ：

\rm Proof ：
  • 当 v > u 时 u 自己都已经删掉了，肯定不能产生贡献。

如上图所示，我们不妨设 u \to v 的路径上必须经过 x(x < u)，那么 x 和 u 一定相互可达，x 会在统计 v 的答案之前被删掉。

于是我们可以发现，若定义两点 (u, v) 有贡献当且仅当 u > v 且 u 和 v 之间可以通过大于 v 的点相互到达，则 h(G) 就是在求解 G 中所有点对的贡献之和。

我们考虑 \rm Floyd 算法的过程，实际上就是在不断求解如果只经过当前已经枚举的这些中转点 k，有哪些 u 可以走到 v. 于是求解 h(G) 只需要从大到小枚举中转点 k，并在 \rm Floyd 的过程中记录下当前 v = k - 1 的答案即可。

进一步观察发现，如果我们按照编号从大到小将边加入图 G，那么必然可以找到一个分界点，使得 u 和 v 恰好变为有贡献的点对。容易发现，这个分界点就是 u 和 v 可以相互到达的路径上编号最小的边的最大值。求解这个最大值是简单的，只需要将初始矩阵修改成边的编号，方程改写为 f_{u, v} = \max\{f_{u, v}, \min\{f_{u, k}, f_{k, v}\}\} 即可。

最后用差分维护一下就可以得到最终答案。

时间复杂度 \Theta(n ^ 3 + m)，常数很小，写得好的话可以通过。

为了进一步优化复杂度，我们摈弃之前使用 \rm Floyd 的想法。

考虑按编号从大到小枚举所有的边，可以发现每对点 (u, v)(u > v) 都会有一个成为有贡献的点对的分界点。

首先计算 v 可以到达 u 的分界点， u 到 v 的分界点可以通过在反图上进行同样的操作来计算。

有两个显然的性质 ：

于是考虑计算每条边加入后有贡献的点对的增量。

如上图所示，设当前加入的边为 x \to y，u_1, u_2, u_3, \cdots 和 v_1, v_2, v_3, \cdots 分别为能到达 x 的点和 y 能到的点。

考虑用 \rm bitset 记录某个点能直接到达的所有点，能到达的所有点和能到达这个点的所有点，不妨分别设它们为 E_u, S_u 和 T_u.

可以发现，若点对 (u, v) 因 x \to y 而增加，需要满足 ：

首先前两个条件可以通过 T_x \cap (U - T_y) 简单地得到，考虑枚举集合中的所有点作为 u 从 y 开始遍历。遍历的过程中，每一步要将 E_v \cap (U - S_u) 中所有编号大于 u 的点作为下一个遍历的点。另外，还要记得随时更新 S_u.

考虑这样做的复杂度为什么是对的。因为每一步都会走到一个合法的 v，所以答案每一步会增加 1. 并且每走一步都需要计算 E_v \cap (U - S_u)，其时间复杂度为 \Theta(\frac{n}{\omega}). 另外，每加入一条边都需要计算 T_x \cap (U - T_y)，其时间复杂度也为 \Theta(\frac{n}{\omega}). 于是总时间复杂度为 \Theta(\frac{n ^ 3 + nm}{\omega}).