解题报告-论对“差分约束”的新理解

上次说整体计数的时候，我们曾经谈到过，可以把“约束关系”看作一条条边而连之，最后形成一堆连通块。

而在我们所说的“约束关系”中，有一部分是这样的：\(a_i\le b_i+c\)。这样的情况有“差分”，有“约束”，所以是“差分约束”。

差分约束一般情形是，\(a>b>c>...\)，让你求 \(a\) 或 \(b\) 或 \(c\dots\) 的最小值。这种情况我们一般只会蹦出来两种思路。

第一种是 \(O(n^V)\) 的大暴力枚举，这个不用说。

第二种就是我们所说的差分约束了。我们把这些约束关系看作一条条边，比如大于关系是边权为 \(1\) 的有向边，而大于等于关系是边权为 \(0\) 的有向边，等于关系是边权为 \(0\) 的无向边。

这样的题目一般要求我们求最值，我们就见一个虚拟原点向所有点连边，然后根据题目要求跑图论算法就可以了。这也是跟我们上次说的一样，把抽象的序列问题转化为具象的图上问题，便于解决。

我们总是在学差分约束的时候觉得简单易懂，但是在做差分约束题的时候却什么都看不出来，直到看到题解才知道，哦，这原来是差分约束！那么如何应对这种情况？

看到形如大于、小于、等于的限制，无论是少还是多，直接上差分约束就对了！不用怕考虑漏了情况，那是后面 \(\texttt{Debug}\) 的事情，而且差分约束的限制条件只会多不会少，不会出现整体改动代码结构的情况。

所以综上所述，差分约束只要是遇到大于等一系列的限制，直接上，一般都有极高的分数。