差分约束&判负环技巧

优化

差分约束时常常需要判断负/正环，需要对SPFA做一些优化，如下：

1. 如果一定有解，使用队列实现SPFA；
2. 如果只用判环，不需要求解，使用栈实现；
3. 如果可能无解，可以把握一下，如果题目大概率无解或者较大数据也会无解，用栈实现，不然用队列。
4. 也可以判断点的入队总入队次数是否大于一个较大值，如果是，那么大概率有环，直接返回真。

差分约束

作用：求不等式组的可行解\(\le / \ge\)，\(a>b\)一般要变成\(a \ge b + 1\)。

原理：

1. 最短路问题中，如果有一条边\((u, v, w)\)，那么\(dist_v \le dist_u + w\)；
2. 最长路问题中，如果有一条边\((u, v, w)\)，那么\(dist_v \ge dist_u + w\)；
   证明：
   以最短路为例。

假设\(dist_v > dist_u + w\)，那么可以令\(v\)最短路径为\(S->...->u->v\)，此时\(dist_v=dist_u+w\)，矛盾。