差分
差分就是一种找出不等式然后将不等式转化为解题方法的算法。
差分的关键
- 构造不等式
- 通过不等式连边
差分约束系统中源点到每个点的距离确定
关于Dist[]的初始化
- 如果将源点到各点的距离初始化为0，最终求出的最短路满足它们之间相互最接近了。
- 如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足它们与该点之间相互差值最大。
- 差分约束系统的确立要根据自己确定的约束条件，从约束点走向被约束点
构造不等式
不等条件一般分两种情况：
- 距离。
- 前N项和。
如何连边
连边一般有两种方法：
- 第一种是连边后求最长路的方法。
- 第二种是连边后求最短路的方法。
例：d[x]-d[y]≥z
- 如果想连边后求最长路，那么将不等式变形为这种形式：d[x]≥d[y]+z（y——x连一条权值为z的边）
- 如果想连边后求最短路，那么将不等式变形为这种形式：d[y]≤d[x]-z（x——y连一条权值为-z的边）
- 如果是别的不等式，也可以根据情况变形。但是要保证的是两个变量(x,y)的系数一定要是正的。而常量则不一定。
差分约束系统
原文：https://www.cnblogs.com/zhangzefei/p/9936630.html
