笔记汇总
我们用 spfa 原因之一是因为 dijkstra 无法判负环,没有抽屉原理应用。
成立原因是 spfa 为三角不等式更新,
本质上就是在数上求最短路(有边界)和图上求的区别。
观察 x1−x2<=c,写成更通用的 x1<=x2+c,
有两点和边作联系,可以联想到最短路中的 distu<=distv+wi(v−>u)
同样 x1>=x2+c,对应了最长路中的 distu>=distv+wi(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 本质迭代,所以是可以滴。
当然,更聪明的是取对数,
2a∗2b=2a+b,假设 2a,2b 是我们需要的,
那么取对数后可以更轻松地维护关系。
如果有多于三个变量,可以枚举其中几个变量的取值
简单题
多,少,至少,至多。
一次是两个人比较,可能会将不等式变式,
A<B+C,A−B<C,B<C−A(C 为常数)
找到变量与常数,结合未知数表示出来就可以变式了。
由于差分约束维护不等式,所以等式为 A==B(A>=B&&A<=B)
正值不等式可开方,倒数异号,负数异号。
中等题
结合实际情况,人数不能为负,
集合本身的序数关系,正序,倒序,某类都在某类右边,
这些可以表示为一系列的不等式来建图。
与前缀和、差分的结合,(区间转化端点)
我们可以维护两点的关系,不等式前缀和
Si>=Si−1+d
Sb>=Sa−1+c
可以维护区间有交换律的不等关系 a+b==b+a(axorb==bxora),
例题
1. 排队布局
难度:2星
难点:差分约束解的判定
如果有负环则无解,没有的话,如果到 dist 没有上界则解可能无限大
负环是求小于等于上界的最大解,本题没有上界,所以我们不能建虚拟源点,
更准确地说,本题没有保证奶牛都小于等于某个值,所以就算有也是无限大。
当然无限大就看 dist[i] 有没有 被迭代了,不是迭代别的点。
本题有两个部分:
1.求负环,
2.求1~n的最短路
第一问需要将所有点置为0,
第二问需要将dist[1]置为0,
所以作两遍。
当然因为求负环并不需要让所有值初始都相等,所以可以合并为1遍。
2. [1007]倍杀测量者
难度:4星
难点:建图、二分
注意二分时是判断一直无解才会输出无解,此时有一个边界不动,
条件就是这个边界在原位(二分范围外)
3. 区间
难度:2星
难点: 建图
本题是区间问题,有前缀和性质,
即,小值域选出的数在大值域中也一定被选出过。
我们尝试根据这个性质出发,构造前缀和版差分约束。
首先就是要构造序列的先后关系,然后填数(最长路会迭代的)
求最少用最长路,记得dist初始化不用正无穷。
4. 雇佣收银员
难度:3星
难点