差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。

• 线性约束：
  • 一般是在一维空间里，给出一些变量，之后告诉你这些变量的大小约束关系，求某个变量的最大值/最小值
  • 比如有$n$个人排成直线，给出之间的距离不能大于/小于某个值，求排成的最长/最短距离
  • 设$d[i]$为第$i$个人的位置，根据大小关系建边即可。
  • 两道例题：HDU3592，[SCOI2011]糖果
• 区间约束
  • 相比于上一个模型，我们处理的对象变成了区间。
  • 从例题POJ 1201来理解这个模型，给定$n$个区间，在数轴上选择最少的点，使得第$i$个区间至少有$c_i$个点。
  • 参考前缀和的思想，我们可以用$d[i]$代表$[0,i]$的区间里选点的数量，则对于区间$[a_i,b_i]$，其中点的数量为$d[b_i]-d[a_i-1]$，联立$c_i$建图。同时注意为了保证$d[i]$合法，还要有$0\leq d[i+1]-d[i]\leq 1$。
  • 另一道例题：POJ 1716

• 考虑松弛过后的最短路$dis$数组，对任意一条长度为$k$从$x$到$y$的有向边，满足$ dis_y \le dis_x + k $，移项得到$ dis_y - dis_x \le k $，这与开头提到的$ x_i - x_j\le k $神似。因此我们将每个变量看成一个点，对每个不等式$ x_i - x_j\le k $连一条从$x_j$到$x_i$的长度为$k$的有向边即可，若图存在负环，意味着通过不等式相加可以得到自己小于自己，那么显然是无解的，否则一定有解，因此判负环即可。
• $x_i - x_j \le k$，则连一条从$x_j$到$x_i$的长度为$k$的有向边。
• $x_i - x_j \ge k$，即$x_j - x_i \le -k$，连一条从$x_i$到$x_j$的长度为$-k$的有向边。
• $x_i = x_j$，等价于$x_i - x_j \le 0$且$x_i - x_j \ge 0$，连一条从$x_i$到$x_j$的长度为$0$的无向边。
• 最后，额外建立一个起点，向每个变量连一条权值为$0$的边，如果有解，最终$dis$数组中的取值就构成了一组可行解。