差分约束系统
差分约束系统
\(x_1-x_2 \leq y_1\)
...
\(x_i-x_j \leq y_i\)
将\(x_i-xj \leq y_i\) 移项，得
\(x_i \leq x_j+y_i\)
可建立一条从\(x_j\)到\(x_i\)的路径，权值为\(y_2\)
将线性规划问题转化为图论问题
差分约束系统的转化:
-
\(x_1-x_2>=y \to x_2-x_1<=-y_1\)
-
\(x_1=x_2 \to x_1-x_2<=0 \quad and \quad x_2-x_1<=0\)
-
\(x_1-x_2<y \to x_1-x_2<=y-1\) (整数解)
-
\(x_1-x_2>y \to x_2-x_1<=-y-1\) (整数解)
对于差分约束系统,有解就必定有无数解
证明:
若 存在一组解 \({x_1,x_2,x_3,...,x_{n-1},x_n}\)
则 \({x_1+k,x_2+k,x_3+k,...,x_{n-1}+k,x_n+k}\) 也是该差分约束系统的解
无解的情况即存在负权环，因为此时SPFA无解
启用超级源点 \(0\) ,设置\(dis_0=w\),向所有节点添加边为 \(x_i-x_0 \leq 0 (i|n)\)
由于\(dis_0=w\),则\(x_0=w\) (一般设\(w=0\));
对于所有的 \(x_i,x_i \leq x_0\) 即 \(x_i \leq w\)
相应地加上\(k\) ,即得到非负解
求最短路，相当于求最大解
求最长路，相当于求最小解
注意：求最长路，要转化为\(x_1 \geq x_2+y\)的形式
一些理解：
观察这个式子：\(x1 \leq x2+y1\),发现如果按图论来说，从\(x2\)点到\(x1\)点最多需要走\(y1\)的路的，如果从\(x2\)点到\(x1\)点建立一条长\(y1\)的路，多的远路不能走，但是少的远路能走，这就构成了最短路算法的松弛基础。于是乎才能使用最短路去求解的。反之最长路就是多的远路能走，短远路不能走，所以是\(x_1 \geq x_2+y\)
标签：...,系统,差分,约束,leq,x2,远路 From： https://www.cnblogs.com/cmachsocket/p/17997454