如果一个系统由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 为 ，b->a为 ，b−>a为w_2 , 这 是 一 个 正 环 ， 即 满 足 , 这是一个正环，即满足 ,这是一个正环，即满足w_1+w_2>0 ， 把 边 转 化 为 不 等 式 就 是 ，把边转化为不等式就是 ，把边转化为不等式就是b>=a+w_1,a>=b+w_2$ ，整理一下就是 0 > = w 1 + w 2 0>=w_1+w_2 0>=w1+w2，又因为 w 1 + w 2 > 0 w_1+w_2>0 w1+w2>0，所以与不等式矛盾，无解。
如果不等式无解，必有上面的矛盾，那么也一定存在正环。
所以无解的充分必要条件是存在正环.
最短路为什么负环代表该约束条件下无解？
最短路中不等式是<=的形式。
加入现在有a->b为 w 1 w_1 w1，b->a为 w 2 w_2 w2, 这是一个负环，即满足 w 1 + w 2 < 0 w_1+w_2<0 w1+w2<0。把边转化为不等式就是 b < = a + w 1 b<=a+w_1 b<=a+w1, a < = b + w 2 a<=b+w_2 a<=b+w2 ，整理一下就是 0 < = w 1 + w 2 0<=w_1+w_2 0<=w1+w2，又因为 w 1 + w 2 < 0 w_1+w_2<0 w1+w2<0，所以与不等式矛盾，无解。
如果不等式无解，必有上面的矛盾，那么也一定存在负环。
所以无解的充分必要条件是存在正环
然后是关于图不连通的情况，即不存在一个点能到达所有点。这个时候是不能得到解的。这个时候需要找一个超级源地，建立一些满足题意的关系。（其实就是多找一些不等式，更加的去约束条件）比如 a i > = 0 a_i>=0 ai>=0等等
下面是一些题目：
POJ - 1364 题解链接
POJ - 1716 题解链接
HDU - 1534
HDU - 3592 题解链接
https://www.luogu.org/problemnew/show/P3084
https://www.luogu.org/problemnew/show/P1250
https://www.luogu.org/problemnew/show/P1993
https://www.luogu.org/problemnew/show/P3275
