差分约束系统是一种特殊的不等式组, 它包含 N 个变量 x1......xn, 以及 M 组限制条件, 每组限制条件都是由两个变量作差
小于一个常数组成的, 形如 X1-X2<=Ck(其中 Ck 为常数). 这类问题我们可以建一个有向图用最短路来解决.
对于 X1-X2<=Ck 我们只需要从点 1 向点 2 连一条有向边, 边权为 Ck, 从任一点开始跑最短路, 如果不存在负环, 那么单源
最短路的解即为原题的一组解.
试想为什么会这样?
果要求 xi − xj ≤ a, 则建立一条从 pj 到 pi 长度为 a 的边
以任意一点为起点求单源最短路, 则一定有 di − dj ≤ a
所以保证了约束条件成立, 如果存在负环那最短路是无限短, 原题就无解.
来源: http://www.bubuko.com/infodetail-3171150.html