「练习题单」差分约束系统
题单介绍
建议配合此[学习笔记](https://www.cnblogs.com/chenyuhe/p/15038365.html)进行练习，效果更佳。
该题单由**学习笔记中的讲解顺序**排序，不按难度排序。
------------
### 差分约束系统导入：
差分约束系统用来解决形似如下的一组不等式：
$\begin{cases}x_{1}-x_{2}\leq 0\\ x_{1}-x_{3}\leq 1 \\ x_{2}-x_{3}\leq1\\ x_3-x_4 \leq 3\\x_5 -x_4 \leq 0\\ x_6 - x_7 \leq 2 \end{cases}$
这一种不等式的特点为：
$1.$ 两个数的差**小于等于**某一个常数。
$2.$ 对于结果，只有两种情况：无解 或 有无数组解。
我们可以将其建模，转换到图上进行操作，通常是进行**单源最短路径**和**单源最长路径**。
这样我们就可以获得每一个不等式的解。
但是有一个问题，我们得到的解不能作为整个不等式组的解。
那应该怎么办？
我们可以将所有点与一个**超级源点**连边，这样获得的解就是整个不等式组的解。
------------
### 作者的小请求：
如果您觉得我写得不错，恳求您的**赞和收藏**qwq。
如果有改进意见，请随时私信我。
### 持续更新 ---> $To$ $Be$ $Continue……$