差分约束系统

Published: by Creative Commons Licence

  • Tags:

等式差分

差分约束系统的问题在于需要处理负环的情况,因此必须使用BF算法或Spfa算法,而这两个算法的最坏时间复杂度为$O(V(V+E))$,这在变量较多的时候往往是不可行的。

一般的差分约束系统的约束样式为: \(x_i-x_j\leq c\) ,但是如果我们只允许等式出现,即: \(x_i-x_j=c\) ,那么我们可以提出一个近线性的算法,判断差分约束系统是否有解,以及找到一组解。

这实际上是带路径压缩的并查集的一个拓展。我们发现路径并查集维护的是一片森林,我们可以为每个顶点赋予一个权值,这个权值表示的是改顶点与顶点所在树的根的差值,即假设顶点为$u$,而顶点所在的树的根为$r$,那么$u$的权重为: \(w(u)=value(u)-value(r)\) 。

这样做的好处是,在执行路径压缩的时候,考虑当前顶点为$u$,$u$的父亲为$p$,$u$所在树的根为$r$,如果$p\neq r$,那么就会发生路径压缩。此时$w(p)$被更新为$w'(p)$,我们可以借助$w'(p)$和$w(u)$得到$w'(u)$:

\[w'(u)=value(u)-value(r)\\ =value(u)-value(p)+value(p)-value(r)\\ =w(u)+w'(p)\]

我们可以将权值的更新联系到并查集的路径压缩中,这样利用并查集的时间复杂度分析可以得出合并和查询操作都是线性的。

之后我们利用路径压缩来处理等式差分,对于等式 \(value(u)-value(v)=c\) 如果$u$和$v$处于相同并查集中,那么就可以用下面的方式进行验证:

\[value(u)-value(v)=value(u)-value(r)-value(v)+value(r)=w(u)-w(r)\]

当然如果处于不同的并查集中,我们就可以将两个并查集合并。

一些差值问题

问题1:给定$n$个未知数:$X_1,\ldots,X_n$。同时给定$m$个约束条件,第$i$个约束条件为$X_{i_1}-X_{i_2}=c_i$。之后要求输出$X_1-X_2,X_2-X_3,\ldots,X_{n-1}-X_n$,如果答案无法确定就输出0。

可以发现我们可以用并查集来维护,每个元素都需要维护到父亲的差值。这样如果两个数处于同一个并查集,就能求解,否则无法确定。

问题2:给定$n$个未知数:$X_1,\ldots,X_n$。同时给定$m$个约束条件,第$i$个约束条件为对于所有$j\in [l_i,r_i]$中所有未知数$X_j$的和为$c_i$。之后要求输出$X_1+X_2,X_2+X_3,\ldots,X_{n-1}+X_n$,如果答案无法确定就输出0。

我们首先将数值转换为前缀和,记$S_i=\sum_{j=1}^iX_i$,那么每个约束条件都确定了两个前缀和的差值,因此就转换为了问题1。而对于要求的$X_i+X_{i+1}$,实际上要求的就是$S_{i+1}-S{i-1}$。

差分约束系统

给定$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$的最小(大)值

要计算$\min x_a-x_b$,我们可以直接以$x_b$为起点跑最短路算法,而这时候顶点$b$到顶点$a$的最短距离就是$\min x_a-x_b$。

同理,要求$\max x_a-x_b$,我们可以直接通过求$-(\min x_b-x_a)$得到。