差分约束

问题形式

解 $n$ 元一次不等式组,每个不等式形如 $x_i-x_j\le k$。

  • 求是否有解
  • 给定解的上/下限,求最大/最小解

方法

用最短路的性质($(u,v,w)\in G\Rightarrow \operatorname{dis}_v\le\operatorname{dis}_u+w$)保证解符合方程(最长路同理)。

  1. 最大解问题转化为最短路,最小解问题转化为最长路。
  2. 将不等式转化为最短路/最长路性质的形式,建边。
  3. 建立源点,向每个节点连出一条长为上/下限的边。
  4. 求单源最短路/最长路,结果就是不等式组的最大/最小解

如果只要求判定是否有解,3、4 步删去,用 SPFA 判定是否有负环/正环。

典例

[SCOI2011] 糖果

因为建完图之后任意边的边权非负,所以一个环内出现正权极为无解,强连通分量缩点后拓扑排序求最长路。

作者

nalemy

发布于

2023-10-18

更新于

2024-03-25

许可协议