1.应用

用图论的方法求解一个每个式子只有两个元的不等式组。 # 2.求法之所以差分约束系统可以通过图论的最短路来解，是因为xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。而求取最值的过程类似于最短路算法中的松弛过程。那么此时问题就已经转化为一个完全的图论问题了，该图论问题的解即为原问题的解，该图论问题无解即原问题无解，易得最短路无解条件为存在负环，即原问题无解条件为存在负环。 ## 负环 ### 定义是一个环，且权值和为负数。当存在负环则此图不存在最短路。 ### 找法使用spfa找 bfs版spfa：判定条件为一个点更新超过n次。 dfs版spfa：判定条件为一个点重复更新（回溯记得清标记）。通常dfs比bfs快，但最坏情况下bfs更稳定。