差分约束

差分约束，虽然是带有“差分”二字，但是实际上通常是归属于图论这一类问题。

差分约束主要的表现形式是求满足一组数值上大小关系条件的最大/最小值。

大小关系条件就是“大于，小于，等于”这种。

通常在拿到一组条件之后，需要确定求的是最大值还是最小值，这会关系到是求最短路还是最长路。

如果是求最大值，一般就是求最短路。与之相对的如果是求最小值就是求最长路。

我们是如何将一组数值上的大小关系条件转换为图论问题的？

我们会将一个关系变为一条边，而在边的两端就是满足这个关系的两个客体。而且通常需要根据是求最大值还是最小值并根据贪心的思想，先将这个关系统一转换为小于等于或者大于等于。

举个例子，对于求最大值来说，需要将所有的关系转换为小于等于，最终的答案就是求满足这一组小于等于关系的一个交集。通过跑最短路，可以不断的去求这个交集。

比如现在有两个值a，b，并且有三个关系

a ≤ b + 1

a ≤ b + 2

a ≤ b + 3

a ≥ 0

b ≥ 0

需要求的是满足这个条件每个数的最大值，假如给a，b分别设置为1，2号点，那么对于前三个关系可以看做是b分别向a连了3条边，权值分别是1，2，3。而对于最后两个条件可以看做是a，b两个点分别向超级源点0连了一条边权为0的边。之后去跑最短路，可以求出a，b两点向超级源点的最短的距离是1，0。所以满足这个条件的最大值就是1，0