什么是差分约束系统？
差分约束系统是一种特殊的N元一次不等式组，它包含N个变量以及M个约束条件，每个约束条件都是由两个变量作差得到的，形如
，其中
是常数。
我们根据题目要求，并用这M个约束条件求出某个不等式的最值，例如
的最大值。
怎么解？
转化：
把上面
不等式稍微变形一下可以得到
，令
，
，
，得到
，是不是联想到了最短路算法？
因此我们可以把这M个不等式转化到图中，例如对于
，则在图中连一条从 j 到 i 的有向边，边权为
。
这时候假如题目需要我们求
的最大值，我们便从图中求出1到N的最短路即可。
为什么是最短路？由于有约束条件，图中可能有更长的路的存在，但是如果选了更长的路，那么就不满足最短路那一条路的约束条件了，即最短路是所有满足条件的路中最长的一条。
解的存在性：
我们知道不等式的解有三种情况：有解、无解、无限个解。
这三种情况对应图中的情况分别是什么样的呢？
有解：在图中可以找到最短路。
无解：图中存在负环，没有最短路。
无限个解：图中我们要求的两点间无法到达，即不连通。
最小值：
如果题目给出的条件形如
，最后要我们求出
的最小值，显然求出1到N的最长路即可。
不等式标准化：
如果题目给出的约束条件既有"≥"也有"≤"该怎么办？
根据题目要求，如果需要求最大值，那么把不等式都转化为"≤"，否则转化为"≥"的形式。
但是要是题目给出了等式该怎么办？
例如
，那么我们可将其转化成两个不等式：
和
。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程