这篇东西瞎写的，作用为防忘，只有一些百度一大把的内容。
定义(wiki)
差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。
如果一个系统由 $n$ 个变量和 $m$ 个约束条件组成，其中每个约束条件形如 $\displaystyle x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])$,则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
解法
求解可转化为单源最短路径问题（有向）。
首先，最短路径等价于求解一组$d_i, 1 \leq i \leq n$，使得图中任意一条有向边满足$d_v \leq d_u + w_{u,v}$，其中$u$、$v$、$w_{u,v}$分别为该有向边的起点、终点、边权。
显然，$d_v \leq d_u + w_{u,v}$可转化为$d_v - d_u \leq w_{u,v}$，此时不等式形式与$x_j - x_i \leq b_k$相同。
因此，以每个变量$x_i$为结点，对于约束条件$x_j - x_i \leq b_k$，连接一条有向边$<i,j>$，边权为$b_k$。再加入超级源$s$，与每个结点$i$连一条有向边$<s,i>$，边权为$0$。对此图跑一遍Bellman-Ford，所得的$d_i$即为一组可行解。
区间约束
Statement
给定一组区间$[l_i, r_i]$，以及一组数$c_i$，求一组点集$S$，使得任一区间$[l_i, r_i]$中均有至少$c_i$个点被选中，且该点集大小$|S|$最小。
Solution
定义$d_i$为区间$[0, d_i]$上被选中的点的数量，对于给定的$[l_i, r_i]$、$c_i$，有：
$$ d_{r_i} - d_{l_i - 1} \geq c_i $$
变形为：
$$ d_{l_i - 1} - d_{r_i} \leq -{c_i} $$
而对于任一$d_i$，有：
$$ 0 \leq d_i - d_{i-1} \leq 1 $$
即：
$$ d_i - d_{i-1} \leq 1 $$
$$ d_{i-1} - d_i \leq 0 $$
模型构造完成。
例题连接
线性约束
Statement
$n$个人编号为$1$~$n$，且按照编号顺序排成直线，任意两人位置不重合。
给定$p$组约束条件$(a_i, b_i, c_i)$，表示$a_i$与$b_i$之间距离不能大于$c_i$。
给定$q$组约束条件$(a_j, b_j, c_j)$，表示$a_j$与$b_j$之间距离不能小于$c_j$。
若排列方案存在，输出$1$与$n$之间的最长可能距离。若不存在，输出$-1$。若无限长，输出$-2$。
Solution
定义$d_i$为$i$所在位置，则对于第一种约束条件，有:
$$ d_{b_i} - d_{a_i} \leq c_i $$
对于第二种约束条件，有：
$$ d_{b_i} - d_{a_i} \geq c_i \space => \space d_{a_i} - d_{b_i} \leq -c_i $$
此处均默认$a_i < b_i$，若$a_i > b_i$，需将二者交换。
另外，根据题目描述，有：
$$ d_i - d_{i-1} \geq 1 \space => \space d_{i-1} - d_i \leq -1 $$
模型构建完成。
若存在负环，则不存在方案。若无法到达$n$，则两者距离可能无限长。否则最长距离即$1$到$n$的最短路长度。
例题链接
对于恒等式
对于形如$x_j - x_i = b_k$的等式，可以分解为$x_j - x_i \leq b_k$与$x_j - x_i \geq b_k$，就ojbk了。