差分约束

算法导论

学习博客

求最大值

$$\begin{cases}
B - A \leq c \\
C - A \leq b \\
C - B \leq a \\
\end{cases}$$

这样求A到C的最大值就是 求min{a+c, b}, 即建图跑最短路。

求最小值

$$\begin{cases}
B - A \geq c \\
C - A \geq b \\
C - B \geq a \\
\end{cases}$$

这样求A到C的最小值就是 求max{a+c,b}, 即建图跑最长路。

不等式的标准化

如果题目中既有小于等于的关系也有大于等于的关系怎么办?

根据题目来,如果要求最大值,就要将所有的大于等于号改为小于等于号,求最小值同理

解的存在性

无解: 出现了负环
无穷多解: 图不连通