差分约束
问题描述:
求解不等式组:
x1 <= x2 + ci
x2 <= x3 + c
.......
xi <= xj + ck
我们发现类似于不等式
if(dist[j] <= dist[t] + w[i]) dist[j] = dist[t] + w[i]
我们发现可以将差分约束问题转化为单源最短路问题,每一个差分约束问题对应一个单源最短路问题
解题步骤:
1. 将每个不等式 xi <= xj + c 转化为 j -> i 边权为 c 的一条边
2. 超级源点,使得其能到达所有边
3.从原点做一遍单源最短路
4.存在负环表示问题无解 => xi <= xj + c 如果存在负环那么xi 一直可以被更新 xi < xi 故无解
问题: 如何转化 xi >= c这类不等式?
我们建立虚拟远源点 xi <= x0 + c 等价于 0 -> i 长度为 c 的边
如图所示, 我们以求xi最大值为例子:
x2 <= x1 + c2
x1 <= x0 + c1
x2 <= x0 + c1 + c2 eg. x2 <= 5 , x2 <= 4 , x2 <= 20 为了满足所有只能取 x2 <= 4,从而求得最大值。xi的最大值等于所有计算出来xi上界的最小值,每一个上界对应一条路径的长度,因此要求最小路。
我们再以求xi最小值为例子:
x2 >= x1 + c2
x1 >= x0 + c1
x2 >= x0 + c1 + c2
eg. x2 >= 5, x2 >= 8, x2 >= 4 为了满足所有条件只能取 x2 >= 8,从而求得最小值。xi的最小值等于所有计算出来下界的最大值,每一个下界对应一条路径,所以我们要求最大路。