差分约束

EricQian · 2020-10-05 17:00:05 · 个人记录

洛谷博客不再更新，搬迁至 差分约束

主要内容

差分约束系统 是一种特殊的 n 元一次不等式组 。

差分约束系统中的每个约束条件 x_i-x_j\le c_k 都可以变形成 x_i\le x_j+c_k 与 x_j\ge x_i-c_k ，这与单源最短路中的三角形不等式非常相似。因此，我们可以把每个变量 x_i 看做图中的一个结点，对于每个约束条件连边。

需要注意的是，有些题目看能会对解的上、下界进行约束，因此我们需要对这些条件处理（这里只考虑对于这 n 个元素 只约束了上界 或 只约束了下界 ）：

• 只约束下界：有 0 号点向每一个点连一条长为 Lim_i 的边，表示第 i 号元素的 下界 为 Lim_i ，如图所示建边：

  题意	转化	连边
  x_a-x_b\ge c	x_a\ge x_b+c	add(b,a,c)
  x_a-x_b\le c	x_b\ge x_a-c	add(a,b,-c)
  x_a=x_b	x_a\ge x_b ， x_b\le x_a	add(a,b,0),add(b,a,0)

  之后对整张图跑 最长路 。

• 只约束上界：有 0 号点向每一个点连一条长为 Lim_i 的边，表示第 i 号元素的 上界 为 Lim_i ，如图所示建边：

  题意	转化	连边
  x_a-x_b\ge c	x_b\le x_a-c	add(a,b,-c)
  x_a-x_b\le c	x_a\le x_b+c	add(b,a,c)
  x_a=x_b	x_a\le x_b ， x_b\le x_a	add(a,b,0),add(b,a,0)

  之后对整张图跑 最短路 。

设 dist[0]=0 ，若存在负环 / 正环，则不等式无解，否则 x_i=dist[i] 是该差分约束系统的一组解 。

最坏情况下（存在负环 / 正环）复杂度为 O(nm) 。

注意：整个图不一定是联通的！

例题

• P1993 小 K 的农场 - 模板 - AC记录

• P2474 [SCOI2008]天平

  P2474 solution

• P4926 [1007]倍杀测量者

  P4926 solution