差分约束

用最短路解决数学问题

差分约束

标准形式

一组数列有 个元素。对这 个元素有 条约束，约束形如下，求 号元素与 号元素差值的最大值：

$$a[i] - a[j] \le b[k]$$

转换为求最短路问题。

如：

一组不等式：

$$\begin{array}{} a[1] - a[0] \le 9 \\ a[1] - a[2] \le 2 \\ a[2] - a[3] \le 2 \\ a[2] - a[0] \le 6 \\ a[3] - a[0] \le 3 \end{array}$$

可以转换为如下图：

解的情况

有负环 - 无解

不存在最短路 - 无穷多解

变形

1. 若要求两个元素差值的最大值，将形式转换为：

$$a[i] - a[j] \ge b[k]$$

1. 若约束为 ，可将约束改为 并且

2. 若约束为 ，且为整数域，可将约束改为