笔记汇总

我们用 $spfa$ 原因之一是因为 $dijkstra$ 无法判负环，没有抽屉原理应用。

成立原因是 $spfa$ 为三角不等式更新，

本质上就是在数上求最短路（有边界）和图上求的区别。

观察 $x1 - x2 <= c$，写成更通用的 $x1 <= x2 + c$，

有两点和边作联系，可以联想到最短路中的 $dist_u <= dist_v + w_i (v -> u)$

同样 $x1 >= x2 + c$，对应了最长路中的 $dist_u >= dist_v + w_i (v -> u)$

我们还可以将 $x1 >= x2 + c$ 变为 $x2 <= x1 - c$

有时候我们得到的图不是连通的，这样求出来的结果很容易出现$INF$。

所以记得加上下界（虚拟源点）。

$x1 <= x0 + c (x0 -> x1)$ 等于设置了边界为 $c$ 的上界，

注意图的语言与人的直觉是相反的，比如它是从右往左读的（后缀表达式）

求解

求最大解要用最短路，因为求最短路可以向下约束至不用约，

求最小解要用最长路，因为求最长路可以向上迭代至不可代。

无解

判环记得要跑完 所有点，避免几个不连通的块有环。

最短路无解为负环，$a <= a-3$

最长路无解为正环，$a >= a+2$

维护信息

不等式关系中的解，最大解，最小解，无解，无穷解。

对应到图里就是最短路，最长路，环，没有被更新。

如果将区间化为端点建图的话，还可以维护，

区间最大解，区间最小解，区间矛盾，区间无穷解。

特殊应用

乘积最长路，除法最长路。

$a >= b * k$，这就是从 $b$ 向 $a$ 连边。

$a >= b / k$，这也是从 $b$ 向 $a$ 连边。

$spfa$ 本质迭代，所以是可以滴。

当然，更聪明的是取对数，

$2 ^ a * 2 ^ b = 2 ^{a + b} $，假设 $2^a，2^b$ 是我们需要的，

那么取对数后可以更轻松地维护关系。

如果有多于三个变量，可以枚举其中几个变量的取值

简单题

多，少，至少，至多。

一次是两个人比较，可能会将不等式变式，

$A < B + C, A - B < C, B < C - A$（$C$ 为常数）

找到变量与常数，结合未知数表示出来就可以变式了。

由于差分约束维护不等式，所以等式为 $A == B (A >= B \&\& A <= B)$

正值不等式可开方，倒数异号，负数异号。

中等题

结合实际情况，人数不能为负，

集合本身的序数关系，正序，倒序，某类都在某类右边，

这些可以表示为一系列的不等式来建图。

与前缀和、差分的结合，（区间转化端点）

我们可以维护两点的关系，不等式前缀和

$S_i >= S_{i-1} + d$

$S_b >= S_{a-1} + c$

可以维护区间有交换律的不等关系 $a + b == b + a(a xor b == b xor a)$，

例题

1. 排队布局

难度：2星

难点：差分约束解的判定

如果有负环则无解，没有的话，如果到 $dist$ 没有上界则解可能无限大

负环是求小于等于上界的最大解，本题没有上界，所以我们不能建虚拟源点，

更准确地说，本题没有保证奶牛都小于等于某个值，所以就算有也是无限大。

当然无限大就看 $dist[i]$ 有没有 被迭代了，不是迭代别的点。

本题有两个部分：

1.求负环，
2.求1~n的最短路

第一问需要将所有点置为$0$，

第二问需要将$dist[1]$置为$0$，

所以作两遍。

当然因为求负环并不需要让所有值初始都相等，所以可以合并为1遍。

2. [1007]倍杀测量者

难度：4星

难点：建图、二分

注意二分时是判断一直无解才会输出无解，此时有一个边界不动，

条件就是这个边界在原位（二分范围外）

3. 区间

难度：2星

难点: 建图

本题是区间问题，有前缀和性质，

即，小值域选出的数在大值域中也一定被选出过。

我们尝试根据这个性质出发，构造前缀和版差分约束。

首先就是要构造序列的先后关系，然后填数（最长路会迭代的）

求最少用最长路，记得$dist$初始化不用正无穷。

4. 雇佣收银员

难度：3星

难点