差分约束学习笔记

发表于 更新于 分类于 ， 阅读次数： Disqus：

概念

差分约束指的是一种 \(n\) 元一次不等式组。令有 \(n\) 个未知数 \(x_1, x_2, \cdots, x_n\)，\(m\) 个形如 \(x_i - x_j \leq c_k\) 不等式，利用差分约束我们可以求出满足条件的解，或判断无解。

实现方法

模型转化

我们先观察 Bellman-Ford 最短路算法。该算法有松弛操作（w(u, v) 指的是边 \(<u, v>\) 的权值） dis[v] = std::min(dis[v], dis[u] + w(u, v))，故在最短路种必定满足 \(dis[v] \leq dis[u] + w(u, v)\)，转化一下即为 \(dis[v] - dis[u] \leq w(u, v)\)。

观察该不等式与差分约束的关系，可把差分约束中 \(x_i - x_j \leq c_k\) 转化为边权为 \(c_k\)，连通 \(<j, i>\) 的有向边。利用此方法可将差分约束转化为图上单源最短路问题。

求解

由于通过转化权值可能为负，我们可使用 Bellman-Ford 或 SPFA 算法。

首先对于不等式 \(x_i - x_j \leq c_k\)，在点 \(j\) 与点 \(i\) 中连一条权值为 \(c_k\) 的边。

由于没有确定的起始点，我们需要再新建一个超级源点，且使超级源点和所有点相连，相连的边的权值均设为 \(0\)。

最后通过 Bellman-Ford 或 SPFA，求出超级源点的单源最短路。最后求出的单源最短路 \(\left \{ dis_1, dis_2, \cdots, dis_n \right \}\) 即为所求解。若图中出现负环，则无解。

注意对于任意常数 \(r\)，\(\left \{ dis_1 + r, dis_2 + r, \cdots, dis_n + r \right \}\) 由于在差分约束中 \(r\) 在运算中会被抵消，故也为所求解。

常见转化

摘自 OI-wiki

公式 转化 连边
\(x_a - x_b \geq c\) \(x_b - x_a \leq -c\) add(a, b, -c)
\(x_a - x_b \leq c\) \(x_a - x_b \leq c\) add(b, a, c)
\(x_a = x_b\) \(x_a - x_b \leq 0, x_b - x_a \leq 0\) add(b, a, 0), add(a, b, 0)

例题

洛谷 P1993 小 K 的农场

显然这是道差分约束的题，同时对输入的三种情况简单地用上述方法转换一下即可。

代码如下（注意开 O2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

const int MAXN = 10000;

int n;
std::vector< std::pair<int, int> > e[MAXN + 1];
int dis[MAXN + 1];

bool bf() {
    bool con;
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;

    for (int i = 0; i <= n; i++) {
        con = false;
        for (int j = 0; j <= n; j++) {
            for (auto each : e[j]) {
                if (dis[each.first] > dis[j] + each.second) {
                    dis[each.first] = dis[j] + each.second;
                    con = true;
                }
            }
        }

        if (!con) break;
    }

    return con;
}


int main() {
    int m;

    std::cin >> n >> m;
    for (int i = 0, op, a, b, c; i < m; i++) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%d", &a, &b, &c);
            e[a].push_back( std::make_pair(b, -c) );
        } else if (op == 2) {
            scanf("%d%d%d", &a, &b, &c);
            e[b].push_back( std::make_pair(a, c) );
        } else {
            scanf("%d%d", &a, &b);
            e[a].push_back( std::make_pair(b, 0) );
            e[b].push_back( std::make_pair(a, 0) );
        }
    }

    // 将0作为超级源点
    for (int i = 1; i <= n; i++) e[0].push_back( std::make_pair(i, 0) );

    std::cout << (bf() ? "No" : "Yes") << std::endl;

    return 0;
}