比如说你现在有一堆不等式：
x1-x2<=a
x2-x3<=b
x3-x4<=c
……
a，b，c都是常数。你要求一组解。
首先可以简单的证明这个方程组要么无解，要么有无数组解。因为如果你找到了一组解，那么把这组解的每个数都加上随便一个什么数k，所有的不等式都还是成立的。
一般来说求最小的非负解的情况比较多。
这时候可以把每一个x都转化为一个点，x1就是点1，x2就是点2，以此类推。每个点的权值就是对应的x。
因为
x1-x2<=a
x2-x3<=b
x3-x4<=c
……
所以
x1<=x2+a
x2<=x3+b
x3<=x4+c
……
其中的a,b,c在建的图里可以表示为点12、点23、点34之间的边的权值。
这样问题就转化为一个最短路问题了。
就是说写最短路的时候都是这么写的么：
if(d[x]>d[y]+dist[x][y]) d[x]=d[y]+dist[x][y];
(d是点权值，dist是边权值)
在这个例子里就是：
if(x1>x2+a) x1=x2+a;
if(x2>x3+a) x2=x3+b;
if(x3>x4+c) x3=x4+c;
做一遍最短路之后，之前的三个不等式肯定都满足（如果不满足就会在if那里被更新的，总之肯定是满足了才会停止算法）
这时候的所有点的权值就是一组解，再根据题目的具体情况统一改动一下就行了。
最短路用Bellman-Ford确实比较好，不过如果用惯了SPFA也行，至少我就习惯都用SPFA
这就是差分约束。vijos近期的笨笨工作室模拟赛里的“笨笨的西瓜种植”就是差分约束题
x1-x2<=a
x2-x3<=b
x3-x4<=c
……
a，b，c都是常数。你要求一组解。
首先可以简单的证明这个方程组要么无解，要么有无数组解。因为如果你找到了一组解，那么把这组解的每个数都加上随便一个什么数k，所有的不等式都还是成立的。
一般来说求最小的非负解的情况比较多。
这时候可以把每一个x都转化为一个点，x1就是点1，x2就是点2，以此类推。每个点的权值就是对应的x。
因为
x1-x2<=a
x2-x3<=b
x3-x4<=c
……
所以
x1<=x2+a
x2<=x3+b
x3<=x4+c
……
其中的a,b,c在建的图里可以表示为点12、点23、点34之间的边的权值。
这样问题就转化为一个最短路问题了。
就是说写最短路的时候都是这么写的么：
if(d[x]>d[y]+dist[x][y]) d[x]=d[y]+dist[x][y];
(d是点权值，dist是边权值)
在这个例子里就是：
if(x1>x2+a) x1=x2+a;
if(x2>x3+a) x2=x3+b;
if(x3>x4+c) x3=x4+c;
做一遍最短路之后，之前的三个不等式肯定都满足（如果不满足就会在if那里被更新的，总之肯定是满足了才会停止算法）
这时候的所有点的权值就是一组解，再根据题目的具体情况统一改动一下就行了。
最短路用Bellman-Ford确实比较好，不过如果用惯了SPFA也行，至少我就习惯都用SPFA
这就是差分约束。vijos近期的笨笨工作室模拟赛里的“笨笨的西瓜种植”就是差分约束题
