浅析差分约束系统 - 洛谷保存站

## 目录
## 1.差分约束系统的定义
## 2.松弛操作
## 3.三角形不等式
## 4.差分约束的原理
## 5.关于无解 
## 6.例题1
## 7.例题2
## 8.例题3
## 9.总结
### by szlhc
## 1.差分约束系统的定义
差分约束系统就是形如 $x_i$ - $x_j$ &le; y 或 $x_i$ - $x_j$ &ge; y 的方程组。

$$ \begin{cases}x[1] -  x[3]  ≤  5 \\x[1] -  x[2]  ≤  2 \\x[2] -  x[1]  ≤  0 \\x[2] -  x[3]  ≤  2 \\x[3] -  x[2]  ≤  -1 \\x[3] -  x[1]  ≤  -2 \\\end{cases}$$

它的其中一组解是：

$$\begin{cases}x[1] = 4\\x[2] = 2\\x[3] = 0\\\end{cases}$$

差分约束系统给出的是一种相对的顺序， 所以它要么有无数组解， 要么无解， 因为如果你能求出一种解， 你给每个数都加上任意实数k， 都可以让方程组成立。
比如上面的方程组的解还有：

$$\begin{cases}x[1] = 2\\x[2] = 0\\x[3] = -2\\\end{cases}$$

## 2.松弛操作

```cpp
if (d[v] > d[u] + w) {
    d[v] = d[u] + w;
}
```
松弛操作指的就是每次由其他点的d值不断优化这个点的d值。

当我们进行完所有的松弛操作后，我们的式子就变成了这个样子：

> $d_v$ &ge; $d_u$ + w;

请记住这个式子。

## 3.三角形不等式

在任意一个三角形内都有两条边之和大于第三边。

设它的三条边的长度分别是a, b, c。

用代数表达就是:

$$\begin{cases}c < a + b\\a < b + c\\b < a + c\\\end{cases}$$

## 4.差分约束系统的原理
仔细观察这两个式子，会发现有相似之处

> $d_v$ &le; $d_u$ + w

> c < a + b --> c <= a + (b + 1)

这不就是最短路吗？！

我们可以把 c < a + b 这个式子理解成建一条从 c 到 a 权值为 b + 1 的边。

那么三角形不等式就变成了这个样子：

$$\begin{cases}c  - > a, w: b + 1\\a  -> b, w: c + 1\\b  -> c, w: a + 1\\\end{cases}$$

将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的单源最短路问题了。

那么问题来了: 怎么插入边呢？

我们的松弛操作是由 u 到 v 的那条边对进行优化。

而我们的三角形不等式就可以转换成插入一条从a到c边权为b + 1的边。

还有一个问题：

如果题目给的是大于怎么办呢？

变成最长路啊！只要把 $d_v$ > $d_u$ + w改成 $d_v$ < $d_u$ + w就行了。

小结一下：

### 小于求最短路得到最大值，
### 大于求最长路得到最小值。(重要)

## 5.关于无解

根据差分约束系统的定义里的总结， 差分约束系统是有可能出现无解情况的。

### 5.1.条件矛盾

顾名思义，满足了条件A就无法满足条件B。

举个例子：

$$\begin{cases}x[1] -  x[2] <= 2 \\x[2] -  x[1]  >=  0 \\\end{cases}$$

这样看不太直接， 可以把它转换成：

$$\begin{cases}x[1] -  x[2] >=  2 \\x[1] -  x[2] <=  0 \\\end{cases}$$

显然无解。

### 5.2.未知数互不关联

其实是有解的， 只不过根据判断无解的方法， 它也算无解， 就是因为没有构成一个强连通分量。

For Example:

$$\begin{cases}x[1] -  x[2]  ≤  2 \\x[3] -  x[1]  ≤  0 \\x[4] -  x[5]  ≤  3 \\x[5] -  x[6]  ≤  1 \\\end{cases}$$

$x_1$, $x_2$, $x_3$ 与 $x_4$, $x_5$, $x_6$无关

### 5.3.无解的判断方法

最短路有负环或最长路有正环即为无解。

## 6.例题1
下面是一道例题：

> [关系运算图](http://gdgzoi.com/problem.php?cid=2212&pid=0)

> #### Description

> 给出一有向图，图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k，则求最小的k，若任何k都无法满足则输出NO。

> 例如下表中最小的k为2。

> 结点1 > 结点2

> 结点2 > 结点3

> 结点2 > 结点4

> 结点3 = 结点4

> 如果存在这样的k，输出最小的k值；否则输出‘NO’。

> #### Input

> 共二行，第一行有二个空格隔开的整数n和m。n表示G的结点个数，m表示G的边数，其中1<=n<=1000, 0<=m<=10000。全部结点用1到n标出，图中任何二点之间最多只有一条边，且不存在自环。

> 第二行共有3m个用空格隔开的整数，第3i-2和第3i-1（1<=i<=m）个数表示第i条边的顶点。第3i个数表示第i条边上的符号，其值用集合{-1，0，1}中的数表示：-1表示‘<’, 0 表示‘=’, 1表示‘>’。

> #### Output

> 仅一行，如无解则输出‘NO’；否则输出最小的k的值。

> #### Sample Input

> 4 4
1 2 -1 2 3 0 2 4 -1 3 4 -1

> #### Sample Output

> 2

思路：

题目给的不等式是a > b, a < b, a = b, 三种。我们可以将a > b如下转换：
 ```cpp
 a > b
 a >= b + 1//整数+1就行了
 ```
 插入一条从b到a边权为1的边。
 
 同理，
 
```cpp
b > a
b >= a + 1
```
 插入一条从a到b边权为1的边。
 
a = b时，我们就直接插入一条从a到b边权为0的边和一条从b到a边权为0的边。

核心代码：
```cpp
int x, y, z;
	for (int i = 1; i <= m; i++) {
		scanf ("%d%d%d", &x, &y, &z);
		if (z == -1) {
			g[y].push_back(node(x, 1));
		} else if (z == 1) {
			g[x].push_back(node(y, 1));
		} else {
			g[x].push_back(node(y, 0));
			g[y].push_back(node(x, 0));
		}
	}
```
剩下的就是一个普通的SPFA了。

## 7.例题2

> [CJB比身高](http://gdgzoi.com/problem.php?cid=2212&pid=2)

> #### Description

> CJB一直觉得自己很高，其实我们都懂的。他总爱跟别人比身高，可是这个悲伤的事实我就不说了吧。CJB所在班级有n个人，CJB的标号为0，其他人的标号为1到n-1。我们知道某些人之间的身高差距的范围。比如CJB和老雷的身高差距为[-3, 2]，意思是：-3≤老雷的身高-CJB的身高≤2。 求CJB所在班级中比CJB高最多的人与CJB的身高差的最大值。如果没有人比CJB高，输出0，如果最高的人最高可以无限大或者输入数据有矛盾的，输出-1。

> #### Input

> 第一行输入两个整数n和m。 然后输入有m行，每行有4个整数u, v, a, b，表示u和v之间的身高差距为[a, b]。

> #### Output

> 输出CJB所在班级中比CJB高最多的人与CJB的身高差的最大值。如果没有人比CJB高，输出0，如果最高的人最高可以无限大或者输入数据有矛盾的，输出-1。

> #### Sample Input

> 3 5

> 0 1 2 5

> 1 2 -2 0

> 2 0 -2 -1

> 2 0 -2 0

> 0 2 1 4

> #### Sample Output

> 4
> #### HINT
> 对于20%的数据，1≤n≤3,-10≤a,b≤10； 对于100%的数据，1≤n≤1000,1≤m≤10000,0≤u,v

思路：

v - u = a ~ b

v - u &ge; a
&& v - u ≤ b

v &ge; u + a 
&& u - v &ge; -b

v &ge; u + a 
&& u &ge; v + (-b)

这道就可以每次插入两条边分别是从u到v边权为a的边和从v到u边权为-b的边。(求最长路)

但这道题还需要处理重边， 伪代码：
```cpp
flag = 1
for i in G[u]
    if G[u,i].v == v
        if w smaller than G[u,i].w
            set new G[u,i].w
        flag = 0;

if flag == 1
    G[u].append(v, w)
```
这样就可以判断重边啦！
附上代码：
```cpp
scanf ("%d%d%d%d", &v, &u, &a, &b);
	flag = 0;
	for (int j = 0; j < g[u].size(); j++) {
		if (v == g[u][j].v) {
			flag = 1;
			g[u][j].w = max (g[u][j].w, a);
		}
	}
	if (!flag) {
		g[u].push_back((node){v, a});
	}
	flag = 0;
	for (int j = 0; j < g[v].size(); j++) {
		if (u == g[v][j].v) {
			flag = 1;
			g[v][j].w = max (g[v][j].w, -b);
		}
	}
	if (!flag) {
		g[v].push_back((node){u, -b});
	}
```
## 8.例题3
> [P3275 [SCOI2011]糖果](https://www.luogu.org/problem/P3275)

> #### Description

> 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

> #### Input

> 输入的第一行是两个整数N，K。

> 接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。

> 如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；

> 如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；

> 如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；

> 如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；

> 如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；

> #### Output

> 输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。

> #### Sample Input

> 5 7

> 1 1 2

> 2 3 2

> 4 4 1

> 3 4 5

> 5 4 5

> 2 3 5

> 4 5 1

> #### Sample Output

> 11

> HINT

> 【数据范围】

> 对于30%的数据，保证 N ≤ 100

> 对于100%的数据，保证 N ≤ 100000

> 对于所有的数据，保证 K<=100000，1 ≤ X ≤ 5，1 ≤ A, B ≤ N

这道题跟上面的关系运算图很像， 但要尤其注意一点：

> ### 小于求最短路得到最大值，

> ### 大于求最长路得到最小值。

这道题要求最小值， 所以要求最长路， 进而要转换成 &ge; 或 > 才对。

附上建边代码：

```cpp
if (x == 1) {// =
	g[u].push_back((node){v, 0});
	g[v].push_back((node){u, 0});
} else if (x == 2) {// <
	g[u].push_back((node){v, 1});
} else if (x == 3) {// >=
	g[v].push_back((node){u, 0});
} else if (x == 4) {// >
	g[v].push_back((node){u, 1});
} else {// <=
	g[u].push_back((node){v, 0});
}
```

## 9.总结：

差分约束系统要想清楚两点：

#### 1.求最短路还是最长路

#### 2.如何建边

正在渲染内容...