【图论】差分约束

更新于 分类于 ， 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

利用图论方法解决不等式为约束条件的解问题

定义

特殊的 nn 元一次不等式组，包含 nn 个变量 x1,x2,…,xnx_{1}, x_{2}, \ldots, x_{n} 以及 mm 个约束条件，求一组解 x1=a1,x2=a2,…,xn=anx_{1}=a_{1}, x_{2}=a_{2}, \ldots, x_{n}=a_{n}, 使得所有的约束条件得到满足, 否则无解。

约束条件： xi−xj≤ckx_{i}-x_{j} \leq c_{k} ，其中 1≤i,j≤n,i≠j,1≤k≤m1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m 并且 ckc_{k} 是常数 (可以是非负数, 也可以是负数) 。

分析

  • 约束条件变形成 xi≤xj+ckx_{i} \leq x_{j}+c_{k} ，把每个变量看做图中的一个结点，从结点 jj 向结点 ii 连一条长度为 ckc_{k} 的有向边。
  • 如果 {a1,a2,…,an}\left\{a_{1}, a_{2}, \ldots, a_{n}\right\} 是该差分约束系统的一组解, 那么对于任意的常数 dd， {a1+d,a2+d,…,an+d}\left\{a_{1}+d, a_{2}+d, \ldots, a_{n}+d\right\} 显然也是该差分约束系统的一组解。
  • 设 dist⁡[0]=0\operatorname{dist}[0]=0 并向每一个点连一条00 边，跑单源最短路（spfa或bellmanford）
    • 若图中存在负环，则给定的差分约束系统无解
    • 否则， xi=dist⁡[i]x_{i}=\operatorname{dist}[i] 为该差分约束系统的一组解。
  • 注意：不可达的情况即二者无约束条件

变式

  • 变式11 ： xi−xj≥ckx_{i}-x_{j} \geq c_{k}
    • 方法一：乘−1-1 改不等式方向
    • 方法二：jj 向ii 建ckc_k 边，跑最长路
  • 变式22 ： xi−xj=ckx_{i}-x_{j} = c_{k} ：改为两个：xi−xj≤ck,xi−xj≥ckx_{i}-x_{j} \leq c_{k}, x_{i}-x_{j} \geq c_{k}
  • 变式33 ： xi−xj<ckx_{i}-x_{j} < c_{k} ：改为xi−xj<ck−1x_{i}-x_{j} < c_{k}-1
  • 注意：涉及边权为负数时，对于跑最短路 or 反图最长路的选择