差分约束系统粗略讲解

差异约束系统是指对以下问题的解释： { x a 1 ? x b 1 ≤ c 1 x a 2 ? x b 2 ≤ c 2 ? x a n ? x b n ≤ c n Q u e a t i o n : max ( x i ? x j ) = ? \begin{cases} x_{a_1} - x_{b_1} \leq c_1\\ x_{a_2} - x_{b_2} \leq c_2\\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ x_{a_n} - x_{b_n} \leq c_n\\ \end{cases}\\ Queation:\max(x_i - x_j) = \ ? ???????????xa1?x b1​ ​≤c1​xa2​​−xb2​​≤c2​            ⋮xan​​−xbn​​≤cn​​Queation:max(xi​−xj​)= ? 这里， x x x数组是受到了很强的约束，又让我们求 max ⁡ ( x i − x j ) \max(x_i - x_j) max(xi​−xj​)，所以这类问题被统称为:

差分约束系统

设我们现在要求这样一道题: { x a 1 − x b 1 ≤ c 1 x a 2 − x b 2 ≤ c 2              ⋮ x a n − x b n ≤ c n \begin{cases} x_{a_1} - x_{b_1} \leq c_1\\ x_{a_2} - x_{b_2} \leq c_2\\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ x_{a_n} - x_{b_n} \leq c_n\\ \end{cases}\\ ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​xa1​​−xb1​​≤c1​xa2​​−xb2​​≤c2​            ⋮xan​​−xbn​​≤cn​​ 那么，我们首先需要先把这道题转换一下，变成： { x a 1 ≤ c 1 + x b 1 x a 2 ≤ c 2 + x b 2              ⋮ x a n ≤ c n + x b n \begin{cases} x_{a_1} \leq c_1 + x_{b_1}\\ x_{a_2} \leq c_2 + x_{b_2} \\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ x_{a_n} \leq c_n + x_{b_n}\\ \end{cases}\\ ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​xa1​​≤c1​+xb1​​xa2​​≤c2​+xb2​​            ⋮xan​​≤cn​+xbn​​​

这时，我们把每一个形如 x a i − x b i ≤ c i x_{a_i} - x_{b_i} \leq c_i xai​​−xbi​​≤ci​的式子都转化成了 x a i ≤ c i + x b i x_{a_i} \leq c_i + x_{b_i} xai​​≤ci​+xbi​​。

然后，我们考虑一个图 G G G,其中 c → d c \rightarrow d c→d,边权为 e e e表示 c c c和 d d d有以下约束关系: d ≤ e + c d \leq e + c d≤e+c(利用 c c c推出 d d d)。

问题问的是 max ⁡ ( x g − x f ) \max(x_g - x_f) max(xg​−xf​),于是我们假设这个图上第 i i i个节点从 f f f出发的最短路为 d i d_i di​,那么我们可以发现:对于每一个约束(如 x a 1 ≤ c 1 + x b 1 x_{a_1} \leq c_1 + x_{b_1} xa1​​≤c1​+xb1​​)，若把 x i x_i xi​替换为 d i d_i di​，可以发现都是可行的。

这就说明， d i d_i di​是一组可行解。

问题问的是 max ⁡ ( x g − x f ) \max(x_g - x_f) max(xg​−xf​)，我们把 x f x_f xf​设为 0 0 0,问题就变成了 max ⁡ ( x g ) \max(x_g) max(xg​),而这恰恰符合最短路，因为 d f = 0 d_f = 0 df​=0。

接下来，我们考虑 G G G的 d f s dfs dfs树。沿着这样一颗 d f s dfs dfs树，我们可以发现:永远满足 x i ≤ d i x_i \leq d_i xi​≤di​，所以说 d i d_i di​是可行解中的最大解。

则答案为 d g d_g dg​。