差分约束学习笔记
问题
给定 n 个变量和 m 个不等式,形为:
xi−xj≤ak
其中 ak 为给定常数
求 xn−x1 的最大值
求解
对于一个 xi−xj≤a ,可以将其转化为 xi≤xj+a
当有 xi−xj/leqa1 、 xj−xk≤a2 时, 则可以转化为 xi≤xk+a1+a2
令 yr 为从 1 号点出发到 r 号点的最短路径,从 j 向 i 连一条长度为 a 的边,则有:
yi≤yj+a
再从 k 向 j 连一条长度为 b 的边,则有:
yi≤yk+a+b
所以可将求 xn−x−1 的最大值转化为求 yn 的最大值,即根据 xi≤xj+a 从 i 向 j 连长度为 a 的边建图,求出从 1 号点到 n 号点的最短路(求最小值即为求最长路)。