求解差分约束系统

差分约束系统是一个N元一次不等式组，由多组形如 $x_i-x_j \leqslant c_k$ 的不等式组成。一个差分约束系统要么无解，要么有无数组解。

Part 1 前置技能

在了解如何判断一个差分约束系统是否有解，或者求出它的一组解之前，我们需要先掌握它的前置技能。

图论基本概念
求单源最短/长路的方法

讲解图论的算法书籍都会讲解单源最短路的求法。在边权非负时，我们通常使用 Dijkstra 算法或 Bellman-Ford算法（以及它们的堆/队列优化算法）。Dijkstra算法不能处理负权存在时的情况，也不能求出单源最长路。Bellman-Ford算法及其队列优化的SPFA算法可以处理边带负权的情况，于是可以通过将边权取相反数的方法求出单源最长路。（见这里）Bellman-Ford算法及其队列优化的SPFA算法都可以判断图中是否存在负环，并且会在 $d[x]>d[y]+w(y,x)$ 时用 $y$ 点更新 $d[x]$ 。

在单源最短路算法结束后，假如图 $G(V,E)$ 中没有负环，那么必有：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

在你搞清楚上面两种SSSP问题求解的算法之后，我们就可以通过以下方式判断负环：

对于Bellman-Ford算法：

每次操作后，总会有一个点收敛。如果没有负环，经过 $n-1$ 轮迭代后必然不会再有点的路径长度被更新。如果迭代 $n-1$ 轮后仍然有点的距离可以被更新，那么说明一定有负环。

对于SPFA算法：

假如在用算法进行处理时，一个点的最短路径经过的边数已经大于 $n-1$ （即必然重复走了很多边和点），那么说明一定有些点可被重复走过，且重复经过这些点之后可以使距离更小。也就是说，图里有负环。使用一个数组 $cnt[]$ 记录每个点当前所求最短路经过了多少边就可以解决这个问题。方法是在用 $x$ 更新 $y$ 时，令 $cnt[y]=cnt[x]+1$ ，并判断是否 $cnt[y] > n-1$ 。

Part 2 求解差分约束系统

在理解Part 1的内容后，我们就可以用它来求解差分约束系统了。

如前所述，差分约束系统中的不等式形式是：

$x_i-x_j \leqslant c_k$

(例如 $x_2 - x_1 \leqslant 6$ )

而一个没有负环的图在跑完单源最短路算法后，满足：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

那么我们能否利用这个形式上的共同性来将求解差分约束系统的问题转化为图上的问题，然后利用图论算法求解？

当然可以。设有图 $G(V,E)$ ，对于差分约束系统中的每组关系 $x_i-x_j \leqslant c_k(i,j \in V)$ ，我们从 $j$ 点向 $i$ 点连接一条权值为 $c_k$ 的有向边。

假如从这个图的某点出发的单源最短路径为 $d[i](i \in V)$ ，满足 $\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$ ，那么这个差分约束系统必然是有解的， $d[i]$ 就是其中一组解。如果有一组解 $\{ x_1,x_2,...,x_n \}$ ，那么 $\{ x_1+k,x_2+k,...,x_n+k \} (k \in \mathbb{R} )$ 也必然是一组解。即它有无数组解。