差分约束专题

希望读者把思路和代码先当成空气,不到万不得已不要看思路,代码最好不要看,可以用来对拍。
首先,对于a-b>=w建模:b->(w)->a
一句经典的话:最短路求出的是最大解,最长路求出的是最小解。
因为求最短路时dist赋的初值是inf,它在松弛变小过程中,一旦满足约束条件就退出,所以是最大值,最长路的情况也是一个道理。(注意,这里的最大值最小值是相对inf和-inf而言的,数学上,差分约束的解是没有最大值和最小值的)
关于求dist[1]和dist[n]之间差最大。
其实我认为求最短路和求最长路都能解决这个问题,对于最短路,新建超级源点,向每个点连边,权0。这相当于增加约束条件dist[i]<=0,因为dist[i]初始化为inf,所以不断松弛直到dist[i]<=0,这是求出的是差距最小的。求最长路的过程也可以这样分析。