浅谈差分约束
差分约束系统 是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,x_2,...,x_n\) 以及 \(m\) 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 \(x_i-x_j\leq c_k\)，其中 \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) 并且 \(c_k\) 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 \(x_1=a_1,x_2=a_2,...,x_n=a_n\)，使得所有的约束条件得到满足，否则判断出无解。
差分约束系统中的每个约束条件 \(x_i-x_j\leq c_k\) 都可以变形成 \(x_i\leq x_j+c_k\)，这与单源最短路中的三角形不等式 \(dist[y]\leq dist[x]+z\) 非常相似。因此，我们可以把每个变量 \(x_i\) 看做图中的一个结点，对于每个约束条件 \(x_i-x_j\leq c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。
注意到，如果 \(\{a_1,a_2,...,a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d\)，\(\{a_1+d,a_2+d,...,a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。
设 \(dist[0]=0\) 并向每一个点连一条权重为 \(0\) 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i=dist[i]\) 为该差分约束系统的一组解。
一般使用 Bellman-Ford 或队列优化的 Bellman-Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 \(O(nm)\)。
一、 求不等式组的可行解
结论
源点需要满足的条件：从源点出发，一定可以走到所有的边。
步骤：
- 先将每个不等式 \(x_i\le x_j+c_k\)，转化成一条从 \(x_j\) 走到 \(x_i\)，长度为 \(c_k\) 的边。
- 找到一个超级源点，使得该源点一定可以遍历到所有边
- 从源点求一遍单源最短路
结果1：如果存在负环，则原不等式组一定无解
结果2：如果没有负环，则 \(dist[i]\) 就是原不等式组的一个可行解
二、 如何求最大值或者最小值，这里的最值指的是每个变量的最值
结论
如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。
问题：如何转化 \(x_i\le c\)，其中 \(c\) 是一个常数，这类的不等式。
方法：建立一个超级源点 \(0\)，然后建立 0 -> i 的边，长度是 \(c\) 即可。
以求 \(x_i\) 的最大值为例：
求所有从 \(x_i\) 出发，构成的多个形如如下的不等式链 \(x_i\le x_j+c_1\le x_k+c_2+c_1\le⋅⋅⋅\le x_0+c_1+c_2+⋅⋅⋅+c_m(x_0=0)\)
所计算出的上界，最终 \(x_i\) 的最大值等于所有上界的最小值。
把上述转换成图论的问题，就是求 \(dist[i]\) 的最小值，即最短路求解
求 \(x_i\) 的最小值 时则完全相反，求一个形如如下不等式链所计算出的下界，最终在所有下界里取最大值 \(x_i\ge x_j+c_1\ge x_k+c_2+c_1\ge⋅⋅⋅\ge x_0+c_1+c_2+⋅⋅⋅+c_m(x_0=0)\)
转换成图论的问题，就是求 \(dist[i]\) 的最大值，即最长路求解