自动搬运

查看原文

来自洛谷，原作者为

	syksykCCC 相信并抓住那些源于热爱，忠于自我的每一个可能性

搬运于2025-08-24 22:31:39，当前版本为作者最后更新于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$ 为值域。