差分约束学习笔记

_Cheems · 2023-08-28 15:16:04 · 个人记录

前言

被 lgj 喷太弱后的 zsw 决定继续摆烂奋发图强。

简介

对于一些 n 元一次不等式组，考虑将每条不等式转换为图上若干条有向边，便可通过求解最短（最长）路来解方程组。而这样建图的思想我们称之为 差分约束。

实现

• 建图

  建图操作可以说是差分约束的精髓了。

  具体的，若有不等式 a-b\le c，其中 c 是常数。移项后得 a\le b+c，我们发现这与图论的三角不等式 dis_v\le dis_u+w 极为相似，那不妨建 e(b,a)=c 的有向边。

  建图后，跑一次最短路，此时 dis_i 就是原方程一组解。

  那么对于 a-b\ge c 该怎么办？同上，建边 e(b,a)=c 的有向边，跑最长路即可。

  不过在实际问题中，往往会同时出现上述两种不等式，此时操作需要统一，也就是要让不等号统一。运用不等式的性质，两边同乘 -1 后会变号，即：a-b\le c\to b-a\ge-c，a-b\ge c\to b-a\le -c。

  还需注意的是，a\le b+c 对应的是最短路，无解的情况就是有负环；a\ge b+c 对应的是最长路，无解则是有正环。注意分辨。

  那么求最短路和最长路有何区别？直观来看最短路对应着最小解集，因为 dis_u 小则 dis_v 小，全局上也是最小。相应的，最长路也对应着最大解集。

  实际情况与上面恰恰相反。为什么？显然 dis_v 可能被多个 dis_{u_i}+w_i 转移，为方便讨论我们令 p_i=dis_{u_i}+w_i。对于最短路而言，最终一定有 dis_v=\min p_i，而回到不等式中就是 a= \min {b_i+c_i}，显然 a 再大一点就无法满足这条最小式子。因此此时的 a 恰好是合法区间的上界，也就对应着最大解集。最长路的情况同上。

  总结：先判断题目是求最小还是最大解集。如果是最大，则先统一形式为 a\le b+c，然后建图跑最短路；反之先统一形式为 a\ge b+c，然后建图跑最长路。

• 模板

  先声明：差分约束更多的是一种建图思想，最短（最长）路算法的选择是多样的。

  • 代码细节

    注意图不一定连通，处理方式：建超级源点，由它向所有点连一条为 0 的边。

    判断负环见 这篇博客，需注意使用超级源点后点数是 n+1。

    • 例题：P5960 【模板】差分约束算法

      人畜无害的模板题，提交记录。