题解 P7624 【[AHOI2021初中组] 地铁】

syksykCCC · 2021-06-20 20:28:24 · 题解

首先看到题目有几个想法：

1. 因为有「不小于」「不大于」这样的限制，考虑差分约束。
2. 因为是环上，可能需要断环为链。

于是不妨设 d_i 表示 1 \to i 的顺时针距离，根据定义，有 d_1 = 0，d_{i+1} \ge d_{i} + 1。

能否只使用 d_i 来描述题目给出的所有性质呢？考虑到问题是在一个环上，而 d 数组无法体现 n 结点与 1 结点之间的距离，所以我们再设一个变量 C 表示环长，显然 C \ge d_{n} + 1。

考虑根据题意建立差分约束系统：

1. 对于第 1 类信息：
   • 若 S_i < T_i，则有 d_{S_i} - d_{T_i} \le -L_i；
   • 否则，有 d_{S_i} - d_{T_i} \le C-L_i。
2. 对于第 2 类信息：
   • 若 S_i < T_i，则有 d_{T_i} - d_{S_i} \le L_i；
   • 否则，有 d_{T_i} - d_{S_i} \le L_i - C。

我们知道，差分约束系统有解的条件为图中没有负环，也就是每个点的最短路是可求的。

那么，如果将 C 视作未知数，图中的每一个环就相当于给定了一个关于 C 的一次不等式，最终 C 的取值范围必然是一段连续的区间。

如何求出 C 的最小值 l 和最大值 r 呢？

以上界 r 为例，考虑二分 x，带入 C = x 进图找负环。

若没有负环，则 r \ge x。

若存在负环，对于该负环的不等式 C 前面的系数 k 进行分类讨论：

1. 若 k = 0，无解，因为这个环无论 C 为何值都是负环。
2. 若 k > 0，则 C 应当增大。
3. 若 k < 0，则 C 应当减小。

答案为 r - l + 1，注意判断无限解的情况。

时间复杂度 O(n(n + m ) \log V)，V 为值域。