差分约束

一个差分约束问题是一个线性规划问题，只不过只有一个限制条件。

Ax$\le$B。

而在A矩阵中每一行只存在一个1和一个-1，其他全为0。

我们可以将这个问题转换为一个图论问题。

对于这样的问题，我们进行建图，如果存在一个$x_i-x_j\le a$，则建立一条从$x_j$到$x_i$的边，边的权重为a。

另外新建一个节点$x_0$，它指向所有的原有未知数节点，权重大小都为0。

这个图被称为约束图。

最终求$x_0$到其他所有节点的最短路，得出的最短路径的长度就是每个未知数的一个可行解。

当存在包含负环时，无解。

接下来用$w表示边的权重，\delta表示最短路$，由于$\delta(v_0,v_j)\le\delta(v_0,v_i)+w(v_i,v_j)$，这是由于右式是一条可行路径，因此最短路小于等于可行路径。因此，$\delta(v_0,v_j)-delta(v_0,v_i)\le\ w(v_i,v_j)$，符合差分约束条件。