这篇文章上次修改于 266 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 305 个字,阅读时长 ≈ 1 分钟

差分约束

博主不保证本内容的正确性,仅做参考

差分约束,最简单的形式就是扔给你一堆不等式让你求可能的解,一般情况下不等式都长这样:$x_{a}-x_{b}\leq y_1$ ,但是如果遇到不长这样的不等式的话,我们就需要把不等式化成这个样子。

那么差分约束这种题怎么做呢,我们把 $x_b$ 换到不等号右边,这样这个不等式就变成了 $x_a \leq y_1 + x_b$ 是不是有点眼熟?这不就是跑最短路时的松弛操作嘛!没错,我们可以把差分约束问题所给出的不等式化成图上的边,不过在非模板题的情况下一般需要进行转化才能连边,最后连完边我们根据题目要求跑最短路/最长路即可

踩过的坑

  1. 要分清楚无解和有任意解的区别!!!!!!

还没写完,先鸽着