差分约束

#差分约束 ##模型 将不等式条件化为：

x1-x2<=v1 x2-x3<=v2 … xi-xj<=vk

求取xi-xj最大值，最小值，或判断该不等式组解的存在性

##做法 对每个x建点 对xi-xj<=vk,建立xj->xi有向边，边权为vk 求max{xi-xj}:xj->xi最短路 求min{xi-xj}:xj->xi最长路 求该差分约束系统解的存在性：

为了避免图不连通的情况， 要添加超级源点S（指向每个点），从它开始最短路 判断负环，有或者图不连通则不存在解，无则存在解。 SPFA判负环：某点进出队超过n次

参考资料

• http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

• http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html