算法图论

差分约束

字数统计: 996字   |   阅读时长: 4分

差分约束模型

问题

差分约束系统是一种特殊的 N 元一次不等式组，有 N 个变量 $X_{1} ~ X_{N}$ 以及 M 个约束条件。

每个约束条件室友两个变量做差得到的：

问题：求出一组解 $X_{i} = a_{i}, i=1,2,…,N$，使得 M 组约束条件均满足。

分析

每个约束条件 $X_{i} - X_{j} \leq c_{k}$ 可以写成 $X_{i}\leq c_{k} + X_{j} $，这与单源最短路中的三角形不等式 d[v] <= d[u] + w 很像。

因此，把每个变量 $X_{i}$ 视为有向图的一个节点 i，对每个约束条件 $X_{i} - X_{j} \leq c_{k}$，从节点 j 向节点 i 连接一条有向边(注意 j, i 与 u, v 的对应关系)，长度为 $c_{k}$。

详细推导过程参考 Joshson 等效变换。

算法

如果 $\{a_{1}, a_{2},…,a_{N}\}$ 是一组解，则对任意常数 $c$，$\{a_{i} + c, i=1,2,…,N\}$ 也是一组解。

不妨先求一组负数解 $\forall i, X_{i} \leq 0$，令 $X_{0} = 0$，相当于多了 $X_{i} - X_{0} \leq 0, i=1,2,…,N$ 这 N 组约束。

在图上增加 $X_{0}$ 点，并从 0 向 i 连接有向边，长度为 0。在新图中求 $X_{0}$ 的单源最短路即求原差分约束系统的一组负数解。

  • 若图中存在负环，则原差分约束系统无解
  • $X_{i} = d[i]$ 是原差分约束系统的一组解

$X_{i} - X_{j} \geq c_{k}$ 改为 $x_{j} - x_{i} \leq c_{k}$

正确性：差限可满足定理，差限不可满足定理

应用

362. 区间

思路

从 0~50000 中选尽可能少的整数，使得每个区间 $[a_{i}, b_{i}]$ 中都有至少 $c_{i}$ 个数被选。

令 s[k] := [0..k] 中最少选择的数字个数，约束：s[bi] - s[ai - 1] >= ci ，这是一个差分约束模型。但是所有的约束都是 xi - xj >= ck 的形式。可以将算法中最短路的部分改为求最长路，有正环则无解。

需要增加几个隐含约束：

  1. s[k] - s[k - 1] >= 0，0 ~ k 选出的数比 0 ~ k-1 多
  2. s[k] - s[k - 1] <= 1，每个数只能被选一次，转换一下编程 >= 的关系 s[k - 1] - s[k] >= -1

  • 建图:

    • -1 ~ 50000 这 50002 个数作为图的节点。
    • k-1 向 k 连接长为 0 的边
    • k 向 k-1 连接长为 -1 的边
    • ai-1 向 bi 连接长为 ci 的边
  • spfa 求单源最长路顺便判定正环：

令 d[-1] = 0，以 -1 为源求单源最长路，因 $ci <= bi - ai + 1$，因此图中没有正环，差分约束系统一定有解。最长路返回后，d[50000] 为答案。

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
61
62
63
64
65
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

struct To
{
    int v, w;
    To(int v, int w):v(v),w(w){}
};

vector<int> spfa(const vector<vector<To>>& g, int st)
{
    int N = g.size();
    vector<int> d(N, -1);
    d[st] = 0;
    queue<int> q;
    q.push(st);
    vector<int> cnt(N, 0);
    cnt[st] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(const To &son: g[u])
        {
            int v = son.v;
            int w = son.w;
            if(d[v] < d[u] + w)
            {
                cnt[v] = cnt[u] + 1;
                if(cnt[v] > N)
                    return {};
                d[v] = d[u] + w;
                q.push(v);
            }
        }
    }
    return d;
}

int main()
{
    int n;
    cin >> n;
    int N = 50002;
    vector<vector<To>> g(N);
    for(int i = 1; i < N; ++i)
    {
        g[i].push_back(To(i - 1, -1));
        g[i - 1].push_back(To(i, 0));
    }
    for(int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back(To(b + 1, c));
    }
    vector<int> d = spfa(g, 0);
    if(d.empty())
        cout << -1 << endl;
    else
        cout << d[N - 1] << endl;
}
  • 也可以把不等式都改为 <= 的形式用常规的负环和单源最短路来做，但是容易出错。
Share