P7516 [省选联考 2021 A/B 卷] 图函数

Alex_Wei · 2022-11-01 10:47:27 · 题解

设一条边的边权为它的编号。

题面描述花里胡哨，我们先推些性质。

将 h 的值摊到每个点对 (i, j) 上。
点对 (i, j)(i \leq j) 最多只会贡献一次，因为计算 f(i, G) 时，枚举 v = j 时 i 已经被删掉了，所以只可能在计算 f(j, G) 且枚举 v = i 时产生贡献。
模拟图函数的计算过程，点对 (i, j)(i \leq j) 产生贡献当且仅当存在 i\to j 的路径 P 和 j\to i 的路径 Q 使得路径上所有点的编号不小于 i。
设 T(i, j) 表示所有这样的路径 P 和 Q 中，边权最小值的最大值。注意是 P 和 Q 的边权最小值而不是 P 或 Q。若 i = j 则 T(i, j) = m。则 (i, j) 会对所有 h(G_t)(0\leq t < T(i, j)) 产生贡献。

至此，存在 n ^ 3 的 Floyd 做法。从大到小枚举中转点 k，枚举 i, j\in [1, n]，令 d_{i, j} 和 \min(d_{i, k}, d_{k, j}) 取 \max，初始值 d_{i, i} = m + 1，d_{i, j}(i\neq j) 为 i\to j 的编号，若不存在则为 0。则 d_{i, j} 表示仅考虑编号不小于 k 的节点时（不包括两端），i\to j 的边权最小值的最大值。因此，在转移 k 之前（或之后），先枚举一遍 j\in [k, n]，则 T(k, j) = \min(d_{k, j}, d_{j, k})。

这个做法严重卡常，需要加一些优化：若 d_{i, k} = 0 则不用再枚举 j，若 i \geq k 则不用再枚举。代码。

考虑对每个 i 求出所有 T(i, j)(i < j)。将所有边按权值从大到小加入，并跳过至少一个端点编号小于 i 的边。在加入权为 w 的边时，若 i\rightsquigarrow j 且 j\rightsquigarrow i，说明 T(i, j) = w。

类似 [ARC092F](https://www.luogu.com.cn/problem/AT_arc092_d)，考虑 bitset 优化。肯定不能先枚举 $i$ 再枚举 $(u, v)$，这样已经 $\mathcal{O}(nm)$ 了。考虑按权值 $w$ 大到小添加每条边 $u\to v$，并 **批量处理每个 $i$**。设 $a_{i, j}$ 表示当前 $i$ 是否可达 $j$。若某个 $i$ 需要从 $v$ 开始 bfs，易知有 $a_{i, u} = 1$，$a_{i, v} = 0$ 且 $i\leq \min(u, v - 1)$。因此，还要维护 $r_{j, i}$ 表示 $i$ 是否可达 $j$，则 $r_u \land \lnot r_v$ 即可找到所有 $i$。此外，维护图的邻接矩阵 $e_{i, j}$ 表示当前 $i\to j$ 是否有边。设 bfs 到 $(i, j)$，则需要更新 $i$ 可达 $to$ 当且仅当 $a_{i, to} = 0$ 且 $e_{j, to} = 1$。$\lnot a_i\land e_j$ 即可找到所有 $to$。反图类似处理。用 `_Find_first` 和 `_Find_next` 找 bitset 中第一个 $1$ 和下一个 $1$，时间复杂度 $\mathcal{O}(n ^ 3 / w)$，是在稠密图上表现最优秀的算法。[代码](https://loj.ac/s/1620461)。