差分约束系统

1.最短路基本性质

如果图中不存在负权回路，则当算法结束以后，对于边(x,y)有 dis[y]≤dis[x]+w ，即 dis[y]−dis[x]≤wdis[y]−dis[x]≤w 成立。

2.差分约束系统

3.差分约束系统与最短路径

4.构图求解

4.1构图

4.2求解

若存在负环，则不等式组一定矛盾。
即：不等式组无解 <-> 存在负环(最短路)/存在正环(最长路)

4.3增加源点

源点需要满足的条件：从源点出发，一定可以走到所有的边（不一定要走到所有的点，某个点走不到表示该点孤立，对应变量无限制，可任意取值）.

从0号点可以走到任意点，则一定可以到达所有边。（反之，可以走到任意边不一定能到达任意点）

4.3解的存在性

，先来看负权圈的情况，如图三-3-1，下图为5个变量5个不等式转化后的图，需要求得是X[t] - X[s]的最大值，可以转化成求s到t的最短路，但是路径中出现负权圈，则表示最短路无限小，即不存在最短路，那么在不等式上的表现即X[t] - X[s] <= T中的T无限小，得出的结论就是 X[t] - X[s]的最大值不存在

再来看另一种情况，即从起点s无法到达t的情况，如图，表明X[t]和X[s]之间并没有约束关系，这种情况下X[t] - X[s]的最大值是无限大，这就表明了X[t]和X[s]的取值有无限多种。

在实际问题中这两种情况会让你给出不同的输出。综上所述，差分约束系统的解有三种情况：1、有解；2、无解；3、无限多解；

附：提高课笔记

最长路 <-> 大于关系
最短路 <-> 小于关系