简介

原理

利用三角不等式的可以用图论的方式求解一个不等式组，设 δ(s,x)\delta(s,x) 为 s→xs \to x 的最短路长度，那么：

δ(s,x)≤δ(s,y)+w(y,x)\delta(s,x)\le\delta(s,y)+w(y,x)

对于下面的不等式组，可以构造一个图来求最短路找到一个可行解。

{x1≤x2+C1x2≤x3+C2⋯xi≤xj+Ci\left\{\begin{aligned} x_1&\le x_2+C_1\\ x_2&\le x_3+C_2\\ \cdots\\ x_i&\le x_j+C_i \end{aligned}\right.

对每个不等式 xi≤xj+Cix_i \le x_j + C_i，变换成三角不等式 δ(s,i)≤δ(s,j)+w(j,i)\delta(s,i)\le \delta(s,j)+w(j,i)，于是就可以构造出有向边 (j,i)(j,i) 边权为 CiC_i 。

步骤

下面是差分约束的一般步骤。

  1. 先将每个不等式转化为一条边。

  2. 找一个超级原点 ss 该点一定可以遍历到所有边。

  3. 从原点求一遍单源最短路。

    1. 如果存在负环，该不等式组一定无解。
    2. 如果没有负环，δ(s,i)\delta(s,i) 就是原不等式的一个可行解。

  4. 如果求每个变量的最小值，应该求最长路；如果求最大值，应该求最短路。

关于最后一点，如果存在最值那么一定存在一个绝对关系 x0≥C0x_0\ge C_0 或 x0≤C0x_0\le C_0，否则任意一组可行解都可以加上任意一个常数，最值就不存在了。

假设已知 x0≤C0x_0 \le C_0，求 xkx_k 的最大值，那么设有两条从 x0→xkx_0 \to x_k 的路径：

x0→⋯→xi→xkx0→⋯→xj→xkxk≤xi+w(i,k)≤⋯≤x0+∑wixk≤xj+w(j,k)≤⋯≤x0+∑wjx_0\to \cdots \to x_i \to x_k\\ x_0\to \cdots \to x_j \to x_k\\ x_k\le x_i+w(i,k)\le\cdots\le x_0+\sum w_i\\ x_k\le x_j+w(j,k)\le\cdots\le x_0+\sum w_j

因为要满足这些不等式组，所以要求的是所有上界的最小值，求最短路。反之亦然。

下面是例题。

区间

给定 n 个区间 [ai,bi][a_i, b_i] 和 整数cic_i。

构造整数集合 Z，使得 ∀i∈[1,n]\forall i\in [1,n]，Z 中满足 ai≤x≤bia_i \le x \le b_i 中的数不小于 cic_i 个。

求 ∣Z∣|Z| 的最小值。

原题链接：AcWing 362。

找差分约束的不等式组，设 SiS_i 为 1∼i1\sim i 中选中数字的个数。

{S0=0Si≥Si−1Si−Si−1≤1⇒Si−1≥Si−1Sb−Sa−1≥c⇒Sb≥Sa−1+c\left \{ \begin{aligned} &S_0=0\\ &S_i\ge S_{i-1}\\ &S_i-S_{i-1}\le 1 \Rightarrow S_{i-1}\ge S_i-1\\ &S_b-S_{a-1}\ge c \Rightarrow S_b\ge S_{a-1}+c \end{aligned}\right.

数据范围给的 a,b∈[0,50000]a,b \in [0, 50000] 这里要用到 a−1a-1 因此给所有输入的 a,ba,b 自增一下，因此最后 ∣Z∣=S50001|Z|=S_{50001}

求最小值，所以用最长路。

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 50010, M = 3*N;
int h[N], e[M], ne[M], w[M], dist[N], idx;
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void spfa() {
    queue<int> q;
    q.push(0);
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    
    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
}

int main() {
    int n; cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= 50001; i++) {
        add(i-1, i, 0);
        add(i, i-1, -1);
    }
    
    while (n--) {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;
        add(a-1, b, c);
    }
    
    spfa();
    cout << dist[50001] << endl;

    return 0;
}

雇佣收银员

一家超市要每天 24 小时营业，为了满足营业需求，需要雇佣一大批收银员。

已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。

经理为你提供了一个各个时间段收银员最小需求数量的清单 R(0),R(1),R(2),…,R(23)。

R(0) 表示午夜 00:00 到凌晨 01:00 的最小需求数量，R(1) 表示凌晨 01:00 到凌晨 02:00 的最小需求数量，以此类推。

一共有 N 个合格的申请人申请岗位，第 i 个申请人可以从 ti 时刻开始连续工作 8 小时。

收银员之间不存在替换，一定会完整地工作 8 小时，收银台的数量一定足够。

现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。

原题链接：AcWing 393。

列不等式，设 xix_i 我们雇佣从第 ii 时开始工作的人数，而 capicap_i 是人数上限，那么：

{0≤xi≤capixi+xi−1+⋯+xi−7≥R(i)\left \{ \begin{aligned} &0\le x_i \le ca p_i\\ &x_i+x_{i-1}+\cdots+x_{i-7}\ge R(i) \end{aligned}\right .

这个式子显然不符合差分约束的形式，可以用前缀和的思想进行转化，设 SiS_i 为前 i(i∈[0,23])i(i\in [0, 23]) 小时开始工作的人数之和。由于需要用到前缀和，所以把下标加一，那么：

{S0=0Si−Si−1≥0Si−Si−1≤capiSi−Si−8≥R(i),i≥8Si+S24−Si+16≥R(i),0≤i≤7\left \{ \begin{aligned} &S_0=0\\ &S_i-S_{i-1} \ge 0\\ &S_i-S_{i-1} \le cap_i\\ &S_i-S_{i-8}\ge R(i),i\ge 8\\ &S_i+S_{24}-S_{i+16}\ge R(i),0\le i \le 7 \end{aligned}\right .

这里可以二分求 S24S_{24} 的最小值，如果图中不存在正环，说明 mid >= ans 执行 r=mid；否则 l=mid+1，这样就能二分出最小值。

由于 S0=0S_0=0，因此可以构造 S24≥S0+S24,S24≤S0+S24S_{24}\ge S_0+S_{24},S_{24}\le S_0+S_{24} 保证 S24S_{24} 为常量。

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
66
67
68
69
70
71
72
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 30, M = 300;
int R[30], cap[N];
int h[N], cnt[N], dist[N], e[M], ne[M], w[M], idx;
bool st[N];
int n;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa(int S24) {

    memset(h, -1, sizeof h);
    idx = 0;
    for (int i = 1; i <= 24; i++) {
        add(i-1, i, 0);
        add(i, i-1, -cap[i]);
        if (i >= 8) add(i-8, i, R[i]);
        else add(i+16, i, R[i]-S24);
    }
    add(0, 24, S24), add(24, 0, -S24);
            
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, -0x3f, sizeof dist);
    queue<int> q;
    q.push(0);
    dist[0] = 0;
    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 24) return false;
                if (!st[j]) st[j] = true, q.push(j);
            }
        }
    }
    return true;
}

int main() {
    int T; cin >> T;
    while (T--) {
        memset(cap, 0, sizeof cap);
        for (int i = 1; i <= 24; i++) cin >> R[i];
        cin >> n;
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            cap[t+1]++;
        }
        
        // 枚举 S24
        int l = 1, r = n;
        while (l < r) {
            int mid = l+r>>1;
            if (spfa(mid)) r=mid;
            else l=mid+1;
        }
        if (spfa(l)) cout << l << endl;
        else cout << "No Solution" << endl;
    }
    return 0;
}

[SCOI2011] 糖果

幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入的第一行是两个整数 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 个小朋友分到的糖果。

小朋友编号从 1 到 N。

原题链接：AcWing 1169。

这里是求最小值，因此是最长路，设最长路长度为 δ(x)\delta(x) 其同样满足三角不等式 δ(x)≥δ(y)+w(y,x)\delta(x)\ge\delta(y)+w(y,x)；所以对于不等式 A≥B+CA\ge B+C 可以建 w(B,A)=Cw(B,A)=C 的边；所有下界的最大值才是最小值。

接下来分析条件。

{x=1,A≥B,B≥Ax=2,B≥A+1x=3,A≥Bx=4,A≥B+1x=5,B≥AA,B≥1\left \{\begin{aligned} &x=1,A\ge B,B\ge A\\ &x=2,B\ge A+1\\ &x=3,A\ge B\\ &x=4,A\ge B+1\\ &x=5,B\ge A\\ &A,B\ge 1 \end{aligned}\right .

最后一个是隐式条件。

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
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

const int N = 1e5+10, M = 2e5+10;
int n, k;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N], cnt[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa() {
    stack<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
        dist[i] = 1;
        cnt[i] = 0;
    }
    
    int times = 0;
    while (q.size()) {
        int t = q.top(); q.pop();
        st[t] = false;
        if (++times >= 3*n) return true;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    
    return false;
}

int main() {
    scanf("%d%d", &n, &k);
    memset(h, -1, sizeof h);
    while (k--) {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(a, b, 0), add(b, a, 0);
        if (x == 2) add(a, b, 1);
        if (x == 3) add(b, a, 0);
        if (x == 4) add(b, a, 1);
        if (x == 5) add(a, b, 0);
    }
    
    if (spfa()) puts("-1");
    else {
        long long ans = 0;
        for (int i = 1; i <= n; i++) ans += dist[i];
        printf("%lld\n", ans);
    }
    return 0;
}

[CF241E] Flights

给定 nn 点 mm 边无边权有向图，求是否存在方案，能够使得 1∼n1\sim n 的所有路径的长度总和相同，并且对于每个边权都满足 1≤w≤21\le w\le 2，如果可以输出 Yes 并按照输入的顺序输出 mm 个边权，如果不可以输出 No。

题目链接：CF241E。

如果满足每个边 (a,b)(a,b) 的条件，可以列出来 2m2m 个不等式：

1≤db−da≤2⇒{db≤da+2da≤db−11\le d_b -d_a \le 2\\ \Rightarrow \begin{cases} d_b\le d_a+2\\ d_a\le d_b-1 \end{cases}

用 SPFA 跑出结果之后直接令边长 (a,b)(a,b) 为差分约束中的 distb−dista\text{dist}_b -\text{dist}_a，这样从 1∼n1\sim n 加起来一定是 distn−dist1\text{dist}_n-\text{dist}_1，能够保证所有路线的边权都相同。

但是还有一个问题没有考虑，就是有些点并不能到终点，对于这些点以及延伸出来的边，它们是否满足这个约束是无关紧要的，如果这些点之间构成环也无所谓，所以我们需要判断哪些点在 1∼n1\sim n 的路径上，简单的方法就是从 1,n1,n 出发分别在正向图和反向图中进行一遍 Flood-fill 标记，只有两次都被标记的点处在路径上。

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
66
67
68
69
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010, M = 15010;
int n, m, L[M], R[M];
int h[N], rh[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool valid[N], rvalid[N], st[N];
#define va(u) (valid[u] && rvalid[u])

void add(int h[], int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int h[], bool st[], int u) {
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(h, st, j);
    }
}

bool SPFA() {
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    q.push(1), dist[1] = 0, cnt[1] = 1;

    while (q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!va(j)) continue;
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] > n) return false;
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    return true;
}

int main() {
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    scanf("%d%d", &n, &m);
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d%d", &a, &b);
        add(h, a, b, 2), add(rh, b, a, 0);
        L[i] = a, R[i] = b;
    }
    dfs(h, valid, 1), dfs(rh, rvalid, n);
    for (int i = 0; i < m; i++) add(h, R[i], L[i], -1);
    
    // 由于题目保证连通, 不用判连通性
    if (!SPFA()) return puts("No"), 0;
    puts("Yes");
    for (int i = 0; i < m; i++) {
        if (va(L[i]) && va(R[i])) printf("%d\n", dist[R[i]] - dist[L[i]]);
        else puts("1");
    }

    return 0;
}