但凡是点上的权值, 我们都将其转换为到虚拟源点的一条边

解决问题

求不等式方程组可行解(xi)的最值(所有不等式的符号相同且都是含等于的, 因为最短路的三角不等式如此, 形式都如: dis[i] <=/>= dis[j] + c的方程组)

问题转化

1. 当我们不等式方程组所有不等号都是<时, 我们可以发现在最短路问题中, 当我们跑一遍单源最短路之后对于每一条j -> i权值为c的边来说, 必定存在dis[i] <= dis[j] + cj(建边) <= dis[k] + ck + cj <= … <= c, 通过放缩知道右边为一个常数(常数不等式), 所以我们只需要确定一个能走完所有边的源点(超级源点, 因为他能到每个顶点, 自然也就能遍历所有顶点的出边咯), 也就是考虑到所有不等式(只要能到任意点, 必然能到任意边, 反之, 不成立), 然后跑一遍最短路, dis[i]就是不等式方程组的可行解了, 若存在负环即原不等式方程组无解(可放缩证明, 提高课差分约束19:00开始).
2. 如果符号都是>的话, 无解就是存在正环, 其他都一样.

解决问题需要条件

1. 常值不等式(xi > c)
2. 关系不等式(xi > xj + c)
3. 能到所有边的超级源点

F.A.Q

建边问题: 对于xi <= c这个不等式怎样建边呢, 我们可以将不等式转化为xi(dis[i]) <= x0(dis[0] == 0) + c, 即由源点连一条到i的边权值为c

总结

求每个自变量的最大值, 跑最短路; 求最小值, 跑最长路;
求最值超级源点一定要是定值(因为需要得到一个边界定值), 求可行解超级源点则不需要是定值
每条链式不等关系都是超级源点到i点的一条路径, 小小取小, 大大取大(考虑到所有不等式)
(前提要满足所有不等式关系)

题型

有很多不等式关系, 求最值问题 -> 转化成图论问题求解

具体讲解复习差分约束视频吧~
y总讲的太好了~