差分约束系统
差分约束系统
给定$n$个未知数$x_1,x_2,\ldots,x_n$，以及$m$个条件：
\[\left\{ \begin{array}{lcr} x_{i_1}-x_{j_1}&\leq &c_1\\ x_{i_2}-x_{j_2}&\leq &c_2\\ \ldots\\ x_{i_m}-x_{j_m}&\leq &c_m\\ \end{array} \right.\]现在要求找出一组满足所有条件的赋值方案，或者报告无解。
这个问题实际上可以转换为最小路径问题。观察第$k$个条件：$x_{i_k}-x_{j_k}\leq c_k$，我们将其稍加转换得到$x_{i_k}\leq c_k+x_{j_k}$，这个不等式是经典的最短路优化公式。
因此如果我们将每个未知数作为顶点，对于第$i$个条件，我们加入一条从$x_{j_k}$到$x_{i_k}$的一条长度为$c_k$的有向边。
找到一组可行解
现在我们考虑如何找到一组解，方案非常简单，我们加入一个新的顶点作为起点，从起点向其它所有顶点连长度为$0$的有向边，之后跑单源最短路径即可。之后将每个未知数的值设置为从起点到它的最短距离即可。
下面我们证明如果我们能成功找到最短路，那么所有约束条件都会被满足：假设第$k$个约束条件未满足，即$x_{i_k}> c_k+x_{j_k}$，注意到这里$x_{i_k}=d(i_k),x_{j_k}=d(j_k)$，而如果我们通过起点到顶点$j_k$，之后通过长度为$c_k$的有向边抵达顶点$i_k$，那么我们就得到了从起点到顶点$i_k$的更短的路径，这与$d(i_k)$是最短路相悖。
找到更多的可行解
假设我们找到了一组可行解，那么我们将所有未知变量加上某个相同常量$t$，就可以得到无数的可行解了。而由于$x_{i_k}-x_{j_k}\leq c_k\Rightarrow (x_{i_k}+t)-(x_{j_k}+t)\leq c_k$，因此所有约束条件也得到了满足。
判断差分约束系统有解
差分约束系统有解当且仅当差分约束系统中无负环。
证明：
如果差分约束系统无负环，那么我们就能找到一个有效的最短路，从而一组可行解。因此无负环是有解的充分条件。如果差分约束系统中有负环$x_{t_1},\ldots, x_{t_m}$，那么就对应的存在$m$个约束条件：
\[\left\{ \begin{array}{lcr} x_{t_1} - x_{t_2} &\leq& c'_1\\ x_{t_2} - x_{t_3} &\leq& c'_2\\ \ldots\\ x_{t_m} - x_{t_1} &\leq& c'_m\\ \end{array} \right.\]我们将$m$个不等式加总得到$0\leq \sum_{i=1}^mc'_i$，而这里提到是负环，因此$0\leq \sum_{i=1}^mc'_i<0$，这显然是不可能的，因此一定无解。
计算$x_a-x_b$的最小（大）值
要计算$\max x_a-x_b$，我们可以直接以$x_b$为起点跑最短路算法，而这时候顶点$b$到顶点$a$的最短距离就是$\max x_a-x_b$。
同理，要求$\min x_a-x_b$，我们可以直接通过求$-(\max x_b-x_a)$得到。
一些例题
题目1：给定$n$个非负未知数$x_1,\ldots,x_n$，以及存在$m$个条件，其中第$i$个条件可以表示为$x_{a_i}-x_{b_i}\leq c_i$。要求判断是否有解，如果有解的话找到一组解使得$\sum_{i=1}^nx_i$最大化或者报告无穷，并找到一组解使得$\sum_{i=1}^nx_i$最小化。
这是典型的差分约束系统问题，我们可以直接利用差分约束系统判断是否有解。
对于最大化总和，我们可以额外加入一个未知数$x_0$，并要求这个未知数只能被赋值为$0$。之后我们以$x_0$为起点跑最短路，到$x_i$的最短距离代表的是$\max x_i-x_0=\max x_i$。此时所有未知数都同时取到最大值，对应的总和也是最大的。
对于最小化总和，我们可以定义另外一组未知数$y_0,y_1,\ldots,y_n$，其中$y_i=-x_i$。之后我们只需要用上面最大化总和的方法求出$\sum_{i=1}^ny_i$后，这时候$-\sum_{i=1}^nx_i$最大，对应的$\sum_{i=1}^nx_i$最小。