『算法-ACM 竞赛-图论』差分约束系统

图论–差分约束系统

先上一张图，看懂了就可以走了！你学会了！

求 x1-x4 的最大值，由题目给的式子 1，2，4 可得 x1-x4>=11,我们来看图中最短路，x1 到 X4 的最短距离也是 11，也就是说差分约束系统就是将给定条件转化为图的过程，说白了还是建图，建完图，就看这个图的性质确定用什么最短路算法即可，是否有无解的情况，依照最短路算法什么时候无解呢？当有负环时无解，也就是说这里如果不确定是否无解的时候，可以用 SPFA 先判断一下，如果存在负环，就直接无解，只存在负的权值的话，就直接 SPFA，优化什么花里胡哨的应改也用不到，全部为正权值的时候直接迪杰斯特拉完事，就这么简单，这个算法主要是考察的怎么将问题转化为差分约束，进而建图，这是这个问题的关键，因为求解只是一遍最短路的事。

证明的话，用三角不等式证明，略。

模版的话，dijkstra+SPFA 判负环+SPFA 负权值最短路即可。

比较简单好想的一个算法。

题目总结：

小 K 的农场！l 可以走了！你学会了！

求 x1-x4 的最大值，由题目给的式子 1，2，4 可得 x1-x4>=11,我们来看图中最短路，x1 到 X4 的最短距离也是 11，也就是说差分约束系统就是将给定条件转化为图的过程，说白了还是建图，建完图，就看这个图的性质确定用什么最短路算法即可，是否有无解的情况，依照最短路算法什么时候无解呢？当有负环时无解，也就是说这里如果不确定是否无解的时候，可以用 SPFA 先判断一下，如果存在负环，就直接无解，只存在负的权值的话，就直接 SPFA，优化什么花里胡哨的应改也用不到，全部为正权值的时候直接迪杰斯特拉完事，就这么简单，这个算法主要是考察的怎么将问题转化为差分约束，进而建图，这是这个问题的关键，因为求解只是一遍最短路的事。

证明的话，用三角不等式证明，略。

模版的话，dijkstra+SPFA 判负环+SPFA 负权值最短路即可。

至于判负环，最好只用 DFS 优化版的 SPFA，这个快一点，有的题目会 TLE！

比较简单好想的一个算法。

题目总结：

小 K 的农场！luogu1993！