日记（周六&&差分约束）

    昨天看的博客其实也是最短路相关的东西，上次没有看完那些博客，又看了一下，然后又研究复习，学习了差分约束。我理解的差分约束就是有很多变量x1，x2，x3。。。xn。他们之间有很多限制条件，我们就是根据这些限制条件来建边，解题。一般有x(n)-x(n-1)<=w。一般不会直接给出这种公式，有些需要自己去推倒。如果是这样的公式，一般求最大值，可以通过数学知识知道要想算出值，需要找到另一个x(n-1)来抵消-x(n-1)这样依次递推下去，这样感觉就像是再x(n)到x(n-1)之间连了一条边，从x(n)走到了x(n-1)，那么要求是最大值，怎么走才是最大那，当然是取最大值的时候，就是边权为w的时候。如果要求x(n)到x1的最大值的话，那么就是求x(n)到x1的连边，而且x(n)-x(n-1)<=w变为x(n)<=x(n-1)+w，这个和最短路松弛操作类似，如果跑完最短路，d(n)有值的话，那么，就是有一个最大值，满足限制条件，完成松弛。如果没有值，那么就是这个图不连通，那么就需要进行一下操作，建立的图可能不联通，我们只需要加入一个超级源点，比如说求取最长路时图不联通的话，我们只需要加入一个点S，对其他的每个点建立一条权值为0的边图就联通了。既然说到这里，无论是最短路还是最长路，都会存在环，这样的话，就不会存在所谓的最大最小值了，那么就需要判环，用spfa即可，n个点中如果同一个点入队超过n次，那么即存在环。

    当x(n)-x(n-1)>=w的话，那么就是相反的，可以把最短路的松弛操作x(n)<=x(n-1)+w，改一下，就变成(n)>=x(n-1)+w，然后求最长路就行了。

    在差分约束中，有些方程需要转化。

    1.X[n-1]-X[0]>=T ,可以进行移项转化为： X[0]-X[n-1]<=-T。

    2.X[n-1]-X[0]<T, 可以转化为X[n-1]-X[0]<=T-1。

    3.X[n-1]-X[0]=T，可以转化为X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T，再利用前两条进行转化即可。

    有很多类似的不等式，都可以类比的转化。其他的操作就是最短路了。