在差分约束系统中：

• 如果求未知数的最大值，那么按小于等于建图后求最短路即可。（因为求最短路是由无穷向下约束得到，，所以得到的一定是最大值）
• 如果求未知数的最小值，那么按小于等于建图后求最长路即可。

注意所有数据的关系，不能漏掉关系，还有与附加源点的关系。

如果是按大于等于建图：

• 求最大值，建图后求最长路；
• 求最小值，建图后求最短路。

因为大于等于建图后，相当于未知数都 -1了，所以求出结果后需要 -1。

可为何可以用最短路解决差分约束问题？在这里我记录自己的理解。

差分约束系统

定义

如果一个系统由\(n\)个变量和\(m\)个约束条件组成，形成\(m\)个形如\(a_i-a_j \leq k \quad (i,j \in [1,n], k为常数)\)的不等式则称其为差分约束系统。

引理

设 $x=(x_1,x_2,\cdots ,x_n)$是差分约束系统 \(Ax \leq b\)的一个解，\(d\) 为任意常数，则 \(x+d=(x_1+d,x_2+d, \cdots ,x_n+d)\) 也是该系统 \(Ax \leq b\) 的一个解

而我们看到的算法解决的问题也便是：在确定一个未知数的情况下，求出这个不等式组中每个 \(a_i\) 的符合不等式的最大值。

理解方式

查阅资料了解到：由于不等式 \(x_i \leq x_j+k\) 和最短路里面的松弛条件：

if(dis[v] > dis[f]+edge[i].w)
    dis[v]=dis[f]+edge[i].w;

颇有相像之处，因此我们可以使用最短路来解决这个问题，具体造作就是对于 \(x_i \leq x_j+k\) 这个不等式，需要从 \(x_j\) 向 \(x_i\) 连一条权值为 \(k\) 的边

蒟蒻实在无法理解这个看起来强词夺理的说法，于是用了另外一种方法理解：

理解新角度

对于任意一个点 \(x_i\) ，假设存在以下约束关系：

$$\begin{cases} x_i \leq x_a+k_a \\\ x_i \leq x_b+k_b \\\ x_i \leq x_c+k_c \\\ x_i \leq x_d+k_d \\\ x_i \leq x_e+k_e \end{cases}$$

可以借助图形来理解

显然，对于上述不等式组，我们手动求解的时候一定是同小取小，也即取 \(x_j+k_j (j=a,b,c,d,e)\) 的最小值
同样的，在最短路径算法中，当我们跑完一次最短路时，\(x_i\) 一定是 \(x_j+k_j (j=a,b,c,d,e)\) 的最小值，并且这个 \(x_i\) 就是满足这个约束条件的最大值

新角度2.0

关于“ \(x_i\) 就是满足这个约束条件的最大值”还有另一种理解方式

我们给 \(x_i \leq x_j+k_j\) 赋予一个意义： \(x_i\) 比 \(x_j\) 最多多 \(k_j\)
那么对于任意一个 \(x_i\) ，都会有大于等于 0 个 \(x_j\) 来约束它。如果有一个 \(x_j=5\) 比 \(x_i\) 最多少 3 ，另一个 \(x_j=2\) 比 \(x_i\) 最多少 1。那么这个时候 \(x_i\) 能够取到的最大值就只有第二个 \(x_j\) 的值加上 1，也就是 3 了。

也就是说，通过分析 \(x_i\) 被 \(x_j\) 的约束情况可以知道这样建图最后求出来的究竟是最大还是最小了

最后发现，这不就是这些不等式组合最短路相似的地方了吗？看来大佬说得对啊！奈何蒟蒻太弱无法理解。

现在还有一个问题待解决：如何确定起点？
根据引理，如果我们得到了一组为负数的解，那么将这组解同时加上一个数也是这个系统的一组解。那么我们不妨设 \(x_0=0\)，然后对每个 \(x_i\) 多列一个不等式 \(x_i \leq x_0\) ，也即 \(x_i \leq x_0 + 0\)。因此，以 \(x_0\) 为起点跑一个单源最短路，就可以得到所有未知数的最大非正数解了，随后便可以任意处置。

不等号倒转

如果不等式中的不等号方向调转，也即变为 \(a_i-a_j \leq k\) 怎么办？

注意到不等式是可以反号的，于是可以转化上述不等式

当然，也可以选择不转化。进而用到上述的方法，可以判断出，如果用最长路算法，可以求出每个未知数在约束范围内的最小值。同样，如果设一个 \(x_0\)，那么求出来的解就是最小的非负整数解

当然，事情并不是永远这么一帆风顺。那当我们遇到这种不等式怎么办：

$$\begin{cases} a-b \geq k_1 \\\ b-c \leq k_2 \\\ c-d \leq k_3 \\\ d=e \\\ f-e \geq k_4 \\\ f-a \leq k_5 \end{cases}$$

首先，关于这个不等式 \(d=e\)，可以化为\(d \leq e\)，\(e \leq d\)
然后，虽然我们可以将这个不等式任意变号求最长或最短路，但是我们还是需要看问题。如果问题是求XXX的最大值，那么就应该去求最短路，繁殖就是求最长路。

解的存在性

显然，不等式组不一定有解。有以下几种情况：

1. 不等式有解；
2. 不等式中的式子相互矛盾，最后出现自己大于（小于）自身的情况；
3. 不等式中的某些未知数之间没有一定的约束关系。

这里不再讨论第一种情况，对于第二种，在最长路上出现便是出现了正环；在最短路上出现就是出现了负环。第三种情况，如果以\(x\)为起点跑程序的话，和\(x\)没有约束关系的值的dis不会被更新。

总结

约束图

在一个差分约束系统 \(Ax \leq b\) 中，\(m \times n\) 的线性规划矩阵 \(A\) 可被看做是 \(n\) 顶点，\(m\) 条边的图的关联矩阵。对于 \(i=1,2, \cdots ,n\)，图中的每一个顶点 \(v_i\) 对应着 \(n\) 个未知量的一个 \(x_i\)。图中的每个有向边对应着关于两个未知量的 \(m\) 个不等式中的一个。

给定一个差分约束系统 \(Ax \leq b\)，相应的约束图是一个带权有向图 \(G=(V,E)\)，其中 \(V={v_0,v_1, \cdots ,v_n}\)，而且 \(E={(v_i,v_j) : x_j-x_i \leq b_k 是一个约束} \cup { (v_0,v_1),(v_0,v_2), \cdots ,(v_0,v_n)}\)。引入附加顶点 \(v_0\)是为了保证其他每个顶点均从 \(v_0\) 可达。因此，顶点集合 \(V\) 由对应于每个未知量 \(x_i\) 的顶点 \(v_i\) 和附加的顶点 \(v_0\) 组成。边的集合 \(E\) 由对应于每个差分约束条件的边与对应于每个未知量 \(x_i\) 的边 \((v_0,v_i)\) 构成。如果 \(x_j-x_i \leq b_k\) 是一个差分约束，则边 \((v_i,v_j)\) 的权 \(w(v_i,v_j)=b_k\)（注意 \(i\) 和 \(j\) 不能颠倒），从 \(v_0\) 出发的每条边的权值均为 0。

定理

给定一差分系统 \(Ax \leq b\)，设 \(G=(V,E)\) 为其相应的约束图。如果 \(G\) 不包含负权回路，那么 \(x=(d(v_0,v_1),d(_0,d_2), \cdots ,d(v_0,v_n))\) 是此系统的一可行解。

求解

由上述定理可知，可以采用Bellman-Ford算法对差分约束问题求解。因为在约束图中，从源点 \(v_0\) 到其他所有顶点间均存在边，因此约束图中任何负权回路均从 \(v_0\) 可达。如果Bellman-Ford算法返回True，则最短路径权给出了此系统的一个可行解；如果返回False，则差分约束系统无可行解。

关于 \(n\) 个未知量 \(m\) 个约束条件的一个差分约束系统产生出一个具有 \(n+1\) 个顶点和 \(n+m\) 条边的约束图。因此采用Bellman-Ford算法，可以再 \(O((n+1)(n+m))=O(n^2+nm)\) 时间内将系统解决。此外，可以用SPFA算法进行优化，复杂度为 \(O(km)\)，其中 \(k\) 为常数。