求解差分约束系统

差分约束系统是一个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}  )也必然是一组解。即它有无数组解。

假如这个图有负环,那么无论如何都有点不满足d[i] \leqslant d[j]+w(j,i)。所以这个不等式组必然没有解。

那假如这个图根本就没有联通呢?只要在每个联通块内不存在负环,那么它也是有解的。我们当然可以对每一个联通块都查找一次负环,但这样太繁琐了。(还要用并查集维护每一块的大小和联通关系)怎么解决?

由上面的推导可以知道,只要一个差分约束系统是有解的,那么它必然有无数组解。我们可以假设它有一组元素均小于等于p的解(p=0则代表求出一组均为负数的解),然后构造一组新的不等式组:

x_i - x_0 \leqslant 0

也就是从点0连一条到点i的权值为0的有向边。

并且令:

d[0]=p

那么我们就可以把这个图联通起来一次跑过了。

Part 3 变形的处理

我们已经能够处理形如x_i-x_j \leqslant c_k的情况了。那如何解决由形如x_i-x_j \geqslant c_k的不等式构成的差分约束系统问题?方法有二:

Way 1 数学变换

很容易将 x_i-x_j \geqslant c_k 变形为x_j-x_i \leqslant -c_k。然后就可以按照之前的步骤求解。(注意Dijkstra算法不可处理带负边权的图)

Way 2改求最长路

对于一个没有正环(走一次边权和为正值)的图,我们可以求解出它每个点从某点出发的单源最长路经d[]

那么一定有:

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

同样的,对于不等式 x_i-x_j \geqslant c_k ,我们连一条从ji的边权为c_k 的有向边。可以设虚点使图联通。假如这个图有正环,那么说明该不等式组无解。反之则有解。

求最长路就只能用Bellman-Ford算法(或其队列优化算法SPFA)了。找正环的方法同负环一样。

需要注意的是,如果我们通过计算最短路来求解查分约束系统,那么其求得的值是满足约束条件的最大值。因为最后\forall i,j \in V,d[i] \leqslant d[j] +w(j,i),也就是说每个点满足的是上界条件。如果用最长路来求解,则求解出的答案是满足条件的最小值,理由同上。

有些时候,我们不需要求解,或者在求解之前要先判断整个图的连通性,可以先从一个虚点向每个点连一条线使得图联通,即使添加这个虚点而增加的条件是我们不需要的。然后再不考虑虚点求解。

你可以尝试这几个题(来自李煜东等的书籍推荐):

1.P2868 [USACO07DEC]观光奶牛Sightseeing Cows

2.UVA1723 Intervals

3.P4878 [USACO05DEC] 布局

参考资料:

留下评论

您的电子邮箱地址不会被公开。