【备忘录】差分约束系统

• 三角不等式
  • 刷完最短路对于任意边\((u,v)\)，满足\(dist_u+w(u,v)\ge dist_v\)
• 差分约束系统
  • 一组形如\(x_a-x_b\le c\)的不等式
  • 形式恰好与三角不等式相同，因此可以用最短路算法求解
  • 可以连一条边权为\(c\)的边\((b,a)\)，将\(dist_a-dist_b\)限制在\(c\)的范围内
  • 当边\((u,v)\)属于最短路径时，\(dist_a-dist_b\le c\)取到等号，即\(dist_a-dist_b\)取到最大值
  • 所以\(\le\)型的不等式刷最短路，得到最大值
  • 同理\(\ge\)型的不等式刷最长路，得到最小值
  • 根据题意将所有等式化成一样的形式，刷最短/长路即可
• Tips
  • 负环/正环：无解（SPFA入队N次）
  • 图不连通怎么办？
    • 直接将所有点入队，根据题意给\(dist_i\)初值
  • \(dist\)没有得到任何更新：任意解