• 导入
  • Question:不等书方程组求解
  • Answer:解法
• 关于差分约束系统
  • 定义
  • 在最短路问题中
  • 解的存在性
    • 解不存在
    • 解无限多
  • 不等书方程组的符号
    • 目的判断
    • 过程标准化
• 差分约束分类
  • 线形约束
  • 区间约束

回顾：最短路三大算法：DIJKSTRA, Floyd, Bellman-Ford(SPFA)
新问题：如何求最长路径？
1.DIJKSTRA按最短路方法直接求最长路
转换成负权求最短路？（Dij算法软肋）
2.常见方案
Floyd算法求每对节点之间的最长路径
因为最长路径也满足最优子结构性质，而Floyd算法的实质就是动态规划
Bellman-Ford算法求最长路径 只要把边权改为原来的相反数即可

导入

Question:不等书方程组求解

给定n个变量和m个不等式，形如： $x_i - x_j \le a_k\quad(0\le i, j\lt n, 0\le k\lt m,\quad a_k$ 已知 $)$ ， 求 $x_{n-1}-x_0$ 的最大值
例如：当 $n=4,\;m=5$ ，不等式组如下，求 $x_3-x_0$ 的最大值

$$x_1-x_0\le2\quad(1)\\x_2-x_0\le7\quad(2)\\x_3-x_0\le8\quad(3)\\x_2-x_1\le3\quad(4)\\x_3-x_2\le2\quad(5)$$

Answer:解法

方案	结果
(3)	$x_3-x_0\le8$
(2)+(5)	$x_3-x_0\le9$
(1)+(4)+(5)	$x_3-x_0\le7$

答案： $7=min\{8,\quad9,\quad7\}$

关于差分约束系统

定义

如果一个系统由n个变量和m个不等书组成，并且这m个不等式均为 $x_i-x_j\le a_k$ 形式，这样的系统成为差分约束( difference constraints )系统。

在最短路问题中

最短路求解中的松弛操作：d[y] = MIN(d[y], d[x] + w(x, y));
最短路全部求出后三角关系：d[x] + w(x, y) >= d[y]
可以再转化一下变成：d[y] - d[x] <= w(x, y)
所以不等式方程组可以通过建立合理模型转化为最短路径问题求解(Bellman-Ford)，经典的数形结合

(1) $\stackrel{5}{\rightarrow}$ (2)
可以表示为 $a_2-a_1\le5$

解的存在性

解不存在

若出现负环，无最短路，解不存在

解无限多

起点s无法到达终点t，表明 $a_t$ 和 $a_s$ 之间并无约束关系，表明 $a_t$ 和 $a_s$ 的取值无限多

不等书方程组的符号

目的判断

$\le\qquad$求最短路
$\ge\qquad$求最长路

过程标准化

如果求两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路
如果求两个变量差的最小值，那么需要将所有不等式转变成">="的形式，建图后求最长路
如果出现 $A - B = C$ 这样的等式，变化成两个不等式 $A - B\ge C$ 和 $A-B\le C$
如果变量都是整数域上的，那么遇到 $A-B\lt C$ 这样的不带等号的不等式，需要变化成带等号的不等式例如 $A-B\le C-1$

差分约束分类

线形约束

N个人的编号为1～N，并且按照编号顺序排成一条直线，任何两人位置不重合，然后给定一些约束条件：
X(X <= 100000)组约束Ax Bx Cx(1 <= Ax < Bx <= N)，表示Ax和Bx的距离不能大于Cx
Y(Y <= 100000)组约束Ay By Cy(1 <= Ay < By <= N)，表示Ay和By的距离不能小于Cy
如果这样的排列存在，输出1-N这两人的最长可能距离，如果不存在，输出-1，如果无限长输出-2。

令第x个人的位置为d[x]，则求解目标：
d[N] - d[1] <= T(最短路)

区间约束

给定n(n <= 50000)个整点闭区间和这个区间中至少有多少个整点需要被选中，每个区间的范围为[ai, bi]，并且至少有ci个点需要被选中，其中0 <= ai <= bi <= 50000
求：[0, 50000]至少需要有多少个点被选中。
例如：3 6 2表示[3, 6]这个区间至少要选择2个点，可以是3,4也可以是4,6（总情况有C(4, 2)种）

用d[i]表示[0, i]这个区间至少有多少点能被选中
对于每个区间[ai, bi]，可以表示成d[bi]-d[ai-1] >= ci
求解目标：d[50000] - d[-1] >= T (最长路)