差分约束算法

差分约束

差分约束系统包含$m$个涉及$n$个变量的差额限制条件，这些差额限制条件每个都是形式为$x_i?x_j\le b_{\in [1,m]}$的简单线性不等式。

通常我们要求解出一组可行解。

最短路差分约束

如果我们把变量看做节点，如果这里用$d_u$表示$di{s}_{S,u}$，那么从$u$到$v$的一条有向边必然满足$d_u+w\ge d_v$，即：
$d_v?d_u\le w$

对比：
$x_v?x_u\le b_i$

因此对于每个限制条件$x_v?x_u\le b_i$，我们可以在图上给$u$到$v$连接一条边权为$b_i$的有向边。
同时建立一个虚拟源点$S$，向着每个点连接一个长度为$0$的边。

如果图中不存在负环，那么可以使用单源最短路径算法求出所有的$d_u$，则$x_i=d_i$就是原问题的一组可行解。如果有负环说明无解。

定理：图中没有负环是差分约束系统有解的充要条件。

充分性显然，因为我们可以构造出一组解。

必要性：
如果图中存在负环，那么说明此差分约束系统无解：
设图中有一个负环，$w_1+w_2+w_3<0$

$x_1+w_1\ge x_2$
$x_1+w_1+w_2\ge x_2+w_2\ge x_3$
$x_1+w_1+w_2+w_3\ge x_3+w_3\ge x_1$
$x_1+w_1+w_2+w_3\ge x_1$
这说明$x_1+一个负数\ge x_1$，这是不可能的，因此这个差分约束系统是矛盾的，无解。

QED.

性质

这样建图跑最短路求出的解是具有一定性质的，具体来说是：

• $x_{i\in [1,n]}\le 0$
• 对于任意差分约束系统的一组解 { x n ′ } \left\{x'_{n}\right\} {xn′?}满足$x_{i\in [1,n]}^{\prime }\le 0$，都有$x_i\ge x_i^{\prime }(i\in [1,n])$，也就称为最大解
• 对于所有解$x_{i\in [1,n]}^{\prime }\le 0$，都有$\underset{i=1}{\sum ^n}{x}_i\ge \underset{i=1}{\sum ^n}{x}_i^{\prime }$

证明：

只需证明性质2，性质1、3显然：
首先考虑虚拟源点$S$的意义，即我们令$x_S$表示一个新量，我们连零边表示：$x_{i\in [1,n]}?x_S\le 0$。
然后我们在跑最短路时强制$x_S=d_S=0$，因此我们连零边实际上限制了：$x_{i\in [1,n]}\le 0$

接下来考虑：
对于$x_i=d_i$，假设其对应的某条从$S$到$i$的最短路径依次经过了点$u_0=S,u_1,u_2,...,u_k=i$，则经过的边对应的不等式为：
$x_{u_j}?x_{u_{j?1}}\le w_j$
求和得到：
$\underset{j=1}{\sum ^k}{x}_{u_j}?x_{u_{j?1}}\le \underset{j=1}{\sum ^k}{w}_j$

由于裂项：
$x_{u_k}?x_{u_0}\le \underset{j=1}{\sum ^k}{w}_j$

由于我们指定了$x_S=0$，也就是说：
$x_i\le \underset{j=1}{\sum ^k}{w}_j$

这给出了此差分约束系统中，满足所有变量都$\le 0$的任意一个解中，$x_i$的一个上界。

同时我们断言这个上界是可以取到的，并且$x_i=d_i=\underset{j=1}{\sum ^k}{w}_j$，原因如下，因为刚才经过的边事实上是由$S$到$i$的最短路径，根据相关理论，我们有：
$di{s}_{S,u_j}?di{s}_{S,u_{j?1}}=w_j$

求和得到：
$\underset{j=1}{\sum ^k}di{s}_{S,u_j}?di{s}_{S,u_{j?1}}=\underset{j=1}{\sum ^k}{w}_j$

由于裂项：
$di{s}_{S,i}=\underset{j=1}{\sum ^k}{w}_j$

因此我们知道$x_i=d_i=di{s}_{S,i}=\underset{j=1}{\sum ^k}{w}_j$，证明上界可以取到。

QED.

最长路差分约束

如果我们用$d_u$表示$S$到$u$的最长路，那么对于有向边$(u,v)$：
$d_u+w\le d_v$
$d_u?d_v\le ?w$
即：
$x_u?x_v\le b_i$

那么$b_i=?w$，即$w=?b_i$

那么从$u$向$v$连接一条长度为$?b_i$的有向边。
在从虚拟源点$S$向着每个点连接一个边权为$0$的有向边。

求出图中的最长路即为差分约束系统的一组解。
同理图中如果存在正环就无解。

性质

这样建图跑最长路求出的解也具有一定性质的，具体来说是：

• $x_{i\in [1,n]}\ge 0$
• 对于任意差分约束系统的一组解 { x n ′ } \left\{x'_{n}\right\} {xn′?}满足$x_{i\in [1,n]}^{\prime }\ge 0$，都有$x_i\le x_i^{\prime }(i\in [1,n])$，也就称为最小解
• 对于所有解$x_{i\in [1,n]}^{\prime }\ge 0$，都有$\underset{i=1}{\sum ^n}{x}_i\le \underset{i=1}{\sum ^n}{x}_i^{\prime }$

证明同理。

其他问题

各类限制转化

通常讨论的差分约束问题往往变量为整数，对于一些其他形式的简单线性不等式可以转化为差分约束问题$x?y\le b$：
$x?y<b?x?y\le b?1$
$x?y\ge b?y?x\le ?b$
$x?y>b?y?x<?b$
$x?y=b?x?y\le b且x?y\ge b$（当然如果全是等式限制直接高斯消元更好）

通常差分约束可能涉及对题意进行差分/前缀和转化。

正解/负解

建最短路得出的解一定是非正解，并且是最大解。
建最长路得出的解一定是非负解，并且是最小解。

同时注意到对一组可行解的每个变量都加$k$之后，这个解仍然是可行解，因此我们可以获得全正/全负解。

后记

于是皆大欢喜。