差分约束
在一个由n个变量和m个约束条件组成的系统，如(x_i-x_j<=k_t)，在不等式组中，要求任意一组特解
将一个不等式变换，(x_j+k_t>=x_i)
这看起来很像spfa三角不等式的判断，如果把整个系统看作一张有向图，这个式子又可以写成
(dis[pos]+val>=dis[to])
这个不等式的反向命题
(dis[pos]+val<dis[to])
必须不成立
即当每一个都无法再对其临接点更新时，整个不等式组成立
利用spfa算法对整个图松弛即可得到一个可行的特解
若此不等式组不存在解，一定会有以下情况发生
(x_i-x_j>k)
(x_j-x_i>k)
放在图中就是一对可以互相松弛的点，成为一个负环，判断图中是否存在负环得到是否有解
自此，spfa可以完美的解决差分约束的问题
——2020.5.22