差分约束系统是拿来获得一些形式特殊的不等式的特解的。这种不等式的形式是xi<=xj+c。注意必须有等号。如果题目中是严格小于那么+/-eps即可。如果是其他形式…想办法变形成这样吧。如果没法变形成这样…那应该不是差分约束的题目- -。

做法是把每一个变量xi看作一个点Ai，记从某个点O出发到Ai的最短路长度为di。那么很显然，如果存在边<u,v>=w那么du+w>=dv，即dv<=du+w。那么就把不等式组中的每一条不等式{xi<=xj+c}变成一条边<Aj,Ai>，权值为c。

注意到这些建图与出发点O的选取无关，而任意选取一个点O所计算出的d数组都满足原不等式组，即为一组解。

那么就可以在这张图上求一些特殊的解了。【这张图很有可能不是连通的。】

如果建出的图中有负圈，那么就没有d数组，也即原不等式没有解。判负圈可以用spfa或者karp等等算法。

那么如果没有负圈，原不等式组就存在解。

对于起点O点的选取决定了求出的是怎样的一组特解。

如果要求解中两个变量的差值xi-xj最大，那么选取Aj作为起点计算最短路。【如果Ai与Aj不连通那么它们的取值就不相关，差值就可以任意小。】

---------------------------------------------------------------------------------

一些小技巧。

如果要求两个变量的差值xi-xj最大，那么反过来就是要求差值xj-xi最小。

如果题目中的一些不等式是规则的【例如xi-x(x+1)>=1】，那么不要把这些不等式所转换成的边加入边集中，而是在处理每个点的时候特殊处理这些规则的边。这么做可以减少内存消耗，而且不知道为什么速度大大提高。