差分约束&最短路
什么是差分约束
如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。
例子：参考http://tsreaper.is-programmer.com/posts/180182
来考虑这个不等式：a-b ≤ c。
我们知道，对于最短路，有这样的不等式：dis(u) ≤ dis(v) + len(v,u) （v,u是由一条长度为len(v,u)的有向边连接的两个点，dis(v)与dis(u)表示起点到达v或u的最短路）。
变形得：dis(u) - dis(v) ≤ len(v,u)，与a-b ≤ c是不是非常相似？
所以，对于形如a-b ≤ c的不等式，我们可以从点b向点a连接一条长度为c的边。这样，我们就可以把不等式转换为图。
求满足条件的最大值该如何建图？求满足条件的最小值呢？
差分约束求最大值时需要将不等式化为<=的格式，因为这样的不等式满足图论中最短路的性质，所以接下来用最短路来求。求最小值需要将不等式化为>=的格式，因为这样的不等式满足图论中最长路的性质，所以接下来用最长路来求。
差分约束解的存在性
最长路为什么正环代表该约束条件下无解？
最长路中不等式是>=的形式。
加入现在有a->b为$w_1 ，b−>a为w_2 ,这是一个正环，即满足w_1+w_2>0 ，把边转化为不等式就是b>=a+w_1,a>=b+w_2$ ，整理一下就是 0>=w1+w2，又因为 w1+w2>0，所以与不等式矛盾，无解。
如果不等式无解，必有上面的矛盾，那么也一定存在正环。
所以无解的充分必要条件是存在正环.
最短路为什么负环代表该约束条件下无解？
最短路中不等式是<=的形式。
加入现在有a->b为 w1，b->a为 w2, 这是一个负环，即满足 w1+w2<0。把边转化为不等式就是 b<=a+w1, a<=b+w2 ，整理一下就是 0<=w1+w2，又因为 w1+w2<0，所以与不等式矛盾，无解。
如果不等式无解，必有上面的矛盾，那么也一定存在负环。
所以无解的充分必要条件是存在正环
图不连通怎么办？
然后是关于图不连通的情况，即不存在一个点能到达所有点。这个时候是不能得到解的。这个时候需要找一个超级源地，建立一些满足题意的关系。（其实就是多找一些不等式，更加的去约束条件）比如 ai>=0等等
下面是一些题目：
https://www.luogu.org/problemnew/show/P3084
https://www.luogu.org/problemnew/show/P1250
京公网安备 11010502036488号