差分约束
差分约束系统
如果一个不等式组由 \(n\) 个变量和 \(m\) 个约束条件组成,形成 \(m\) 个形如 \(x_j-x_i\leq k\)(\(i,j\in[1,n]\) 且 \(k\) 为常数)的不等式,则称其为 差分约束系统。换句话说,解决差分约束问题就是求解一组变量的不等式组。
问题转化
对于 \(x_j-x_i\le k\),我们会发现它类似最短路网络中的三角不等式 \(d_v-d_u\le w_{<u,v>}\),那是否可以通过最短路的形式解决呢?显然是可以的。
我们首先把这个不等式化一下,成 \(x_j\le x_i+k\)。可以推出,\(x_j\) 的最大值只可能是 \(x_i+k\),最小不限。
那我们再次假设如果 \(x_j\) 跟 \(x_{i'}\),\(x_{i''}\),\(x_{i'''}\) 都有关,我们就可以得到三个不等式,即一个不等式组:
\[\begin{cases} x_j\le x_{i'}+b \\\ x_j\le x_{i''}+b \\\ x_j\le x_{i'''}+b \end{cases}\]
那么 \(x_j\) 满足所有不等式下的最大值应该是:
\[\min\{x_{i'}+b,x_{i''}+b,x_{i'''}+b\}\]
因为要满足所有不等式,所以必须要取最小值来满足所有的不等式。不等式解集应该是范围更小的那一个。
注意,我们上面提到的 \(i\) 都可以模拟成 \(j\) 的 前继。
那么我们可以再次简化模型。
假设有多个 \(x_i\) 是 \(x_j\) 的前继,那么我们就可以得到一个式子,满足原不等式组的求解:
\[x_j=\min\{x_i+b\}\]
这不就是最短路嘛!
此时,可将每个变量看成一个顶点,并设一个超级源点 \(x_0\),它连向每个顶点(除了自身)且边权为 \(0\),这时再对每一个不等式 \(x_j-x_i\le k\) 连一条边权为 \(k\) 的有向边 \(<i,j>\),此时用 \(x_j\) 表示超级源点到 \(j\) 的最短路,用 \(x_i\) 表示超级源点到 \(i\) 的最短路,由于有边 \(<i,j>\) 存在,从而有 \(x_j\le x_i+k\),即为原不等式的变形。
在有解的情况下,跑一遍最短路,最短路的答案 \(d_i\) 正是原不等式组的一个解 \(x_i\)。
使用“最长路”求解也是可以的。
连边方法
差分约束问题可以转化为最短路或最长路问题,所以两种转化也就形成了两种不同的连边方法。
- 连边后求最短路 将 \(x_j-x_i\le k\) 变形为 \(x_j\le x_i+k\),即从 \(i\) 到 \(j\) 连一条边权为 \(k\) 的边。加入超级源点后求最短路,得到 \(x_i\le 0\) 所有 \(x\) 最大解。
- 连边后求最长路 将 \(x_j-x_i\le k\) 变形为 \(x_i\ge x_j-k\),即从 \(i\) 到 \(j\) 连一条边权为 \(-k\) 的边。加入超级源点后求最长路,得到 \(x_i\ge 0\) 所有 \(x\) 最小解。
显而易见地,两种方法求出来的解大概率是不同的。
判断无解
若求最短路,图中存在负环,则该不等式组无解。
此时,即可放心大胆地 SPFA,只需在 SPFA 的同时用一个数组来记录每个顶点入队次数,如果一个顶点入队次数大于 \(n\),说明该图存在负环。对于 DFS_SPFA,只需看当前顶点如果访问过,说明该图存在负环。
模板
1 |
|
例题
P6145 [USACO20FEB]Timeline G
https://www.luogu.com.cn/problem/P6145。
连边方式:
1 | for i from 1 to n |
之后求最长路。
P4878 [USACO05DEC]Layout G
https://www.luogu.com.cn/problem/P4878。
连边方式:
1 | for i from 1 to ML |
之后求最短路。差分约束题还是有很多条件在里面的,仔细看题是正道。