差分约束学习笔记

问题

给定 nn 个变量和 mm 个不等式,形为:

xixjakx_i - x_j \leq a_k

其中 aka_k 为给定常数

xnx1x_n - x _1 的最大值

求解

对于一个 xixjax_i - x_j \leq a ,可以将其转化为 xixj+ax_i \leq x_j + a

当有 xixj/leqa1x_i - x_j /leq a_1xjxka2x_j - x_k \leq a_2 时, 则可以转化为 xixk+a1+a2x_i \leq x_k + a_1 + a_ 2

yry_r 为从 11 号点出发到 rr 号点的最短路径,从 jjii 连一条长度为 aa 的边,则有:

yiyj+ay_i \leq y_j + a

再从 kkjj 连一条长度为 bb 的边,则有:

yiyk+a+by_i \leq y_k + a + b

所以可将求 xnx1x_n - x-1 的最大值转化为求 yny_n 的最大值,即根据 xixj+ax_i \leq x_j + aiijj 连长度为 aa 的边建图,求出从 11 号点到 nn 号点的最短路(求最小值即为求最长路)。