差分约束算法

标签：不等式 移项 差分 约束 leq 算法 x2 x1 dis

\[\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} \]

转化为最短距离：
对于任意的一个不等式\(x_1-x_2\leq y\)可以看作从\(x_1\)这个点到\(x_2\)这个点的距离小于等于y，如果对该不等式移项，可以获得\(x_1 \leq x_2 + y\)。那么移项之后的不等式可以理解为以x2为起点x1为终点，这两点之间的距离不能超过y。初始化一个超级源点，该源点到所有的点的距离都是0

if(dis[x1] > dis[x2] + y) dis[x1] = dis[x2] + y;

转化为最长距离：
不等式\(x_1-x_2\leq y\)移项获得\(x_1 - y\leq x_2\)，可以理解为从x1到x2之前有权值为-y的边，并且\(dis[x2]\)要大于\(dis[x1] - y\)

      if (dis[x2] < dis[x1] + y) 
        dis[x2] = dis[x1] + y;

标签：不等式,移项,差分,约束,leq,算法,x2,x1,dis
From： https://www.cnblogs.com/GuanStudy/p/17175204.html