差分约束入门+理解（太菜了）

差分约束经典的形式就是给出一组不等式，让你求出满足这组不等式的解（所有的解值最大或最小）。

例如：这组不等式

要求x2、x1的差值范围那么就是把1、2式相加即得
x2-x1<=5 (1)
x2-x1<=1 (2)
很明显，取x2-x1<=1，就是右边取最小值，因为x2、x1要同时满足上面两个不等式，所以x2、x1差的范围小于等于1。
由以上我们可以得到什么启发呢？
我们知道，最短路算法是通过（如下图）这样松弛边的

这个和不等式有什么关系呢？(看下面这个图）

x3-x1<=2 转换为1->3这条边 权值为2
x2-x3<=3 转换为3->2这条边 权值为3
x2-x1<=1 转换为1->2这条边 权值为1
从图中可以看出x1到x2的最短路即为1，也就是他们取得满足不等式时右边的值即 x2-x1<=1;
所以当给你一组不等式，要你求满足这组不等式的解时，你只需要建一个图跑下最短路即可。
还是下面这几个式子：

要你求满足这几个不等式的解，即求x1、x2、x3
你只需要建一个超级源点s指向x1、x2、x3，边的权值设为0，然后以源点为出发点跑一遍最短路就可求出来了，当然也有不满足的情况，就是当图中存在负权环路的时候，就不存在最短路，即无解的情况。

由图可知，s到x1点的最短路为0，到x2为0，到x3也为0；
所以得出一组解为{0，0，0}（这里是刚好图中的边都为正值，如果存在负权边最短路就不一定是0了）当然，解也不止一个，你可以对解加上任意一个数都会满足以上不等式，因为求的是差值，例如，同时加上10{10,10,10}这组解也满足以上不等式。
为什么要加上一个超级源点呢？
因为根据不等式建出来的图可能不连通，加上一个超级源点可以保证连通。
另一方面，为什么用最短路处理之后所得的值就是解呢？（前提图中不存在负权回路）
因为当dis[v]>dis[u]+w这个条件成立的时候会令dis[v]=dis[u]+w 即取得不等式=号，这也就是为什么当你在构造不等式的时候当不等式没有等号的时候要构造一个等号，不然就不能使用最短路去求解。
即x2-x1<c时，可以转化为x2-x1<=c-1。
另外，上面那组不等式里都是<=号，也就是说格式是一样的，如果出现x2-x1>=c,那么需要乘个-1把不等号方向改变即可变成x1-x2<=-c。
另外，也有求最长路的，即
x3-x1>=2 (1)
x2-x3>=3 (2)
x2-x1>=1 (3)
这个式子要求x2-x1差值取值范围，就是右边取得最大值
即
x2-x1>=5 (1)+(2)
x2-x1>=1 (3)
取 x2-x1>=5
所以要反过来求最长路。