如何用Bellman和SPFA算法改写差分约束系统学习POJ1364的解题思路？

本文共计2230个文字，预计阅读时间需要9分钟。

差分约束系统【概念】：对一个序列，给定m个不等式形式a+b=k，同时满足这m个不等式的解是否存在。

【学习】：我是通过一个三角形不等式来理解的。

例如以下三个不等式：（摘自上）

差分约束系统

：对于一个序列。

给出m个不等式，形如a+b<=k

问，同时满足这m个不等式的解存不存在。

：

我是通过一个三角不等式看懂的。

如下三个不等式：（摘自上述博客）

B - A <= c (1)

C - B <= a (2)

C - A <= b (3)

我们想要知道C - A的最大值，通过(1) + (2)，可以得到 C - A <= a + c，所以这个问题其实就是求min{b, a+c}。 将上面的三个不等式按照 三-1 数形结合

图三-2-1

三角不等式。将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的最短路问题了。