差分约束系统
差分约束系统
给定n个未知数x1,x2,…,xn，以及m个条件：
{xi1−xj1≤c1xi2−xj2≤c2…xim−xjm≤cm现在要求找出一组满足所有条件的赋值方案，或者报告无解。
这个问题实际上可以转换为最小路径问题。观察第k个条件：xik−xjk≤ck，我们将其稍加转换得到xik≤ck+xjk，这个不等式是经典的最短路优化公式。
因此如果我们将每个未知数作为顶点，对于第i个条件，我们加入一条从xjk到xik的一条长度为ck的有向边。
找到一组可行解
现在我们考虑如何找到一组解，方案非常简单，我们加入一个新的顶点作为起点，从起点向其它所有顶点连长度为0的有向边，之后跑单源最短路径即可。之后将每个未知数的值设置为从起点到它的最短距离即可。
下面我们证明如果我们能成功找到最短路，那么所有约束条件都会被满足：假设第k个约束条件未满足，即xik>ck+xjk，注意到这里xik=d(ik),xjk=d(jk)，而如果我们通过起点到顶点jk，之后通过长度为ck的有向边抵达顶点ik，那么我们就得到了从起点到顶点ik的更短的路径，这与d(ik)是最短路相悖。
找到更多的可行解
假设我们找到了一组可行解，那么我们将所有未知变量加上某个相同常量t，就可以得到无数的可行解了。而由于xik−xjk≤ck⇒(xik+t)−(xjk+t)≤ck，因此所有约束条件也得到了满足。
判断差分约束系统有解
差分约束系统有解当且仅当差分约束系统中无负环。
证明：
如果差分约束系统无负环，那么我们就能找到一个有效的最短路，从而一组可行解。因此无负环是有解的充分条件。如果差分约束系统中有负环xt1,…,xtm，那么就对应的存在m个约束条件：
{xt1−xt2≤c′1xt2−xt3≤c′2…xtm−xt1≤c′m我们将m个不等式加总得到0≤∑mi=1c′i，而这里提到是负环，因此0≤∑mi=1c′i<0，这显然是不可能的，因此一定无解。
计算xa−xb的最小（大）值
要计算maxxa−xb，我们可以直接以xb为起点跑最短路算法，而这时候顶点b到顶点a的最短距离就是maxxa−xb。
同理，要求minxa−xb，我们可以直接通过求−(maxxb−xa)得到。
一些例题
题目1：给定n个非负未知数x1,…,xn，以及存在m个条件，其中第i个条件可以表示为xai−xbi≤ci。要求判断是否有解，如果有解的话找到一组解使得∑ni=1xi最大化或者报告无穷，并找到一组解使得∑ni=1xi最小化。
这是典型的差分约束系统问题，我们可以直接利用差分约束系统判断是否有解。
对于最大化总和，我们可以额外加入一个未知数x0，并要求这个未知数只能被赋值为0。之后我们以x0为起点跑最短路，到xi的最短距离代表的是maxxi−x0=maxxi。此时所有未知数都同时取到最大值，对应的总和也是最大的。
对于最小化总和，我们可以定义另外一组未知数y0,y1,…,yn，其中yi=−xi。之后我们只需要用上面最大化总和的方法求出∑ni=1yi后，这时候−∑ni=1xi最大，对应的∑ni=1xi最小。