什么是差分约束系统？

什么是差分约束系统？

差分约束系统是一种特殊的N元一次不等式组，它包含N个变量以及M个约束条件，每个约束条件都是由两个变量作差得到的，形如，其中是常数。

我们根据题目要求，并用这M个约束条件求出某个不等式的最值，例如的最大值。

怎么解？

转化：

把上面不等式稍微变形一下可以得到，令，，，得到，是不是联想到了最短路算法？

因此我们可以把这M个不等式转化到图中，例如对于，则在图中连一条从 j 到 i 的有向边，边权为。

这时候假如题目需要我们求的最大值，我们便从图中求出1到N的最短路即可。

为什么是最短路？由于有约束条件，图中可能有更长的路的存在，但是如果选了更长的路，那么就不满足最短路那一条路的约束条件了，即最短路是所有满足条件的路中最长的一条。

解的存在性：

我们知道不等式的解有三种情况：有解、无解、无限个解。

这三种情况对应图中的情况分别是什么样的呢？

有解：在图中可以找到最短路。

无解：图中存在负环，没有最短路。

无限个解：图中我们要求的两点间无法到达，即不连通。

最小值：

如果题目给出的条件形如，最后要我们求出的最小值，显然求出1到N的最长路即可。

不等式标准化：

如果题目给出的约束条件既有"≥"也有"≤"该怎么办？

根据题目要求，如果需要求最大值，那么把不等式都转化为"≤"，否则转化为"≥"的形式。

但是要是题目给出了等式该怎么办？

例如，那么我们可将其转化成两个不等式：和。