浅谈最短路和差分约束

差分约束系统

n 个未知量 x1, x2 ⋯ xn，m 个不等式条件 这样的一组不等式就是一个差分约束系统，差分约束系统的求解可以巧妙的转化为最短路问题

和最短路的关系

先移项，得到 ，可以发现和最短路中的三角不等式非常相似，。因而可以转化成最短路问题，具体来说，先对不等式建图，每个不等式都可看成边，让 j 向 i 连一条权为 c 的边，此图上跑最短路，得到的 disi 就是一组满足条件的解。

转化的充要性证明

限制条件转化为有向边，跑最短路得到的 dis 满足 ，把 disu, disv 看成 xu, xv 的话，也就是 ，因而当最短路有解，也就是没有负环，原不等式就有解，且解就为 dis，必要性成立

思考一下变量关系，若是关系无环比如说是一条链，容易想到，此时的不等式和最短路都是有解的。若是变量关系成环，设存在一个有向环 ，对应的边权依次为 ，，，。

由每条边对应的约束，有 将上述不等式逐项代入相消可得 若不等式组有解，则必有 否则会出现矛盾，而这也意味着图中不存在负环，所以此时最短路也是有解的，充分性成立

因此，不等式组有解等价于图中的最短路有解，这个转化是充分且必要的

最小解和最大解

若是 ，这样从 u 跑到 v ，得到 ，可以发现 xv 的解正好取等，即最大解，也可推出其他变量的解都为最大解。若我们想要最小解，那么让 ，这样从 u 跑到 v，不就有最小解了吗。但是，这样还是跑最短路吗？再观察 ，回想一下我们前面的证明，可以发现最短路的关键性质，，和此不等式不再契合。然而有没有什么满足 这个性质呢？仔细一看，这不正是最长路的性质吗，对的，我们直接跑最长路就可以了，相似的，无解条件为存在正环

因此， 这样 建边跑最短路能得到最大解， 这样 建边跑最长路能得到最小解

负权图最短路

有负权边后，dijkstra 就不再适用了，因为 dijkstra 基于贪心思想，每走一步期望的 dis 都应该是单调不减的。所以我们需要可以在负权图上跑最 短/长 路，且能判 负/正 环的算法

Bellman-Ford O(n ⋅ m)

此算法暴力的进行 n − 1 轮，每轮都从所有的点向所有方向走，这样最短路一定可以延展出来，因为一条简单路最多 n − 1 条边嘛。正是因为它非常之暴力，所以能处理 dijkstra 处理不了的负权问题。还能检测负环，可以额外跑一轮，若还有 dis 可以更新的话，那只能是存在负环了

MYCODE

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 1e18;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> gra(n + 1);
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        if(w >= 0){
            gra[u].push_back({v, w});
            gra[v].push_back({u, w});
        }
        else gra[u].push_back({v, w});
    }

    vector<ll> dis(n + 1, inf);
    dis[1] = 0;
    for(int k=0; k<n-1; k++){ // 尝试 n - 1 轮松弛
        for(int i=1; i<=n; i++){
            if(dis[i] == inf) continue;
            for(auto [v, w] : gra[i]){
                dis[v] = min(dis[v], dis[i] + w);
            }
        }
    }

    bool neg = false; // 额外跑一轮 // neg 为 ture 则存在负环
    for(int i=1; i<=n; i++){
        if(dis[i] == inf) continue;
        for(auto [v, w] : gra[i]){
            neg |= dis[i]+w < dis[v];
        }
    }
    
    cout << (neg? "YES":"NO") << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

SPFA O(k ⋅ m)

在 Bellman-Ford 中，最短路还没延展到的点的遍历是多余的。所以可以用一个队列，存已经延展的点，从这些点去扩展。spfa 非常类似换掉 pq 的 dijkstra，它是 Bellman-Ford 算法的队列优化版，复杂度为 O(k ⋅ m) ~ O(n ⋅ m)。此外，也有启发式的 spfa，不过比较玄学，启发的大致思想是，更容易松弛别人的点就放队列前，在此不过多赘述

MYCODE

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 1e18;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> gra(n + 1);
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        if(w >= 0){
            gra[u].push_back({v, w});
            gra[v].push_back({u, w});
        }
        else gra[u].push_back({v, w});
    }

    bool neg = false;
    int s = 1; // 源点 // 可能要建超级源点
    vector<bool> inq(n + 1);
    vector<int> cnt(n + 1); // 当前到 u 的最短路的边数
    vector<ll> dis(n + 1, inf);
    dis[s] = 0, inq[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty() && !neg){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(auto [v, w] : gra[u]){
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if(!inq[v]) q.push(v), inq[v]=true;
                if(cnt[v] >= n){
                    neg = true;
                    break;
                }
            }
        }
    }
    
    cout << (neg? "YES":"NO") << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

题目链接: 【模板】负环

差分约束例题

【模板】差分约束

我们先建一个超级源点 s，其对所有点建一条权为 0 的边，主要目的是让图连通，方便处理，也相当于加了限制条件 ，而且这样操作是不影响可解性的，因为若有解，则整体平移后也是一个解。建好图，从 s 开始跑一下最短路就可以了。

注意 : 加源点后图中就是 n + 1 个节点了 , 要判断 cnt[v] ≥ n + 1

MYCODE

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 <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 3e18;

// 差分约束 就是 负权图最短路
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> gra(n + 1);
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> v >> u >> w;
        gra[u].push_back({v, w});
    }
    for(int i=1; i<=n; i++){
        gra[0].push_back({i, 0});
    }

    bool neg = false;
    int s = 0;
    vector<bool> inq(n + 1);
    vector<int> cnt(n + 1);
    vector<ll> dis(n + 1, inf);
    dis[s] = 0, inq[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty() && !neg){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(auto [v, w] : gra[u]){
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;

                if(!inq[v]) q.push(v), inq[v]=true;

                if(cnt[v] >= n+1){ // 有源点, 所以是 n+1 !
                    neg = true;
                    break;
                }
            }
        }
    }
    if(neg){
        cout << "NO" << '\n';
        return;
    }

    for(int i=1; i<=n; i++){
        cout << dis[i] << " \n"[i == n];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

SP116 - Intervals

题意

n 个区间 [ai, bi]，每个区间至少选 ci 个整数。满足这 n 条限制的情况下，至少要取多少个整数

解析

每条限制可转化成 ，很容易想到差分约束。关键是如何建图去描述这个问题，思考 pre 数组的特点，大概为 ，，这两个条件已经足够描述出合法的前缀和数组，我们将此额外限制加入图中，这样就可以得到合法的解

整理一下 : 这题需要求最小解，我们要跑最长路。此外，这题值域有 0，我们简单平移一下即可

MYCODE

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 1e18;

// 差分约束 , 最长路 , 求最小解
/*
  好像不需要判正环

*/
const int MX = 5e4+1;
void solve(){
    int n; cin >> n;
    vector<vector<pii>> gra(MX + 1);
    for(int i=1; i<=n; i++){
        int u, v, c;
        cin >> u >> v >> c;
        u++, v++, c;
        gra[u-1].push_back({v, c});
    }
    for(int i=1; i<=MX; i++){
        gra[i-1].push_back({i, 0}); // 0 <= pi - pi-1 <= 1 // 两者都要
        gra[i].push_back({i-1, -1});
    }

    int s = 0;
    vector<bool> inq(MX + 1);
    vector<ll> dis(MX + 1, -inf);
    dis[s] = 0, inq[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(auto [v, w] : gra[u]){
            if(dis[u] + w > dis[v]){ // 改这里即为最长路
                dis[v] = dis[u] + w;

                if(!inq[v]) q.push(v);

                inq[v] = true;
            }
        }
    }
    cout << dis[MX] << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

A - 2019 CCPC Harbin

和上面那道题比较相似，但多了一个二分，限制条件要想好，注意 spfa 中的剪枝，否则会 tle

题意

n 个立方体一排，涂色，有两种限制，分别有 M1，M2 个。第一种：[Li, Ri] 中的立方体涂色个数  ≥ k，第二种：[Li, Ri] 外的立方体涂色个数  ≥ k。求满足限制的最小染色立方体数

(n ≤ 3000, 0 ≤ M1, M2 ≤ 3000)

解析

和上面的题比较相似。不同点在于限制二是 ，多一个变量，容易想到二分 pren 去掉一个变量，这样就转化成了差分约束问题。我们二分 pren，将 设为 ，因为前缀和的性质，我们还有 ，。

限制条件即为 : 要注意的是，为了解的正确性，我们至少将所有的限制边都遍历过一遍，而此题仅从超级源点出发不是很能保证满足这个条件。因为 而 ，可能会有 ，这导致点 n 不会入队，也就会使得点 n 相关的限制边没有遍历到，从而导致错解。解决办法为，不建超级源点 s，而是直接将每个点都加入队列中，这样一定可以保证每个限制边都遍历过

另，此人竟然提交了惊人的 77 发之后 ? ? 终于算是过掉了这题 ? ? QAQ

( 这人也太菜了，我无言以对 )

MYCODE

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
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 3e18;

// 差分约束 , 最长路 , 求最小解
/*
  单调性 
  pn 越大 , 条件越宽松 , 更容易有解
  容易证明, 无解有解对应的 pn 区间连续

*/

void solve(){
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<tuple<int, int, int>> q1(m1), q2(m2);
    for(auto& [l, r, c] : q1) cin >> l >> r >> c;
    for(auto& [l, r, c] : q2) cin >> l >> r >> c;

    vector<bool> inq(n + 1);
    vector<int> cnt(n + 1);
    vector<ll> dis(n + 1, -inf);
    vector<vector<pii>> gra(n + 1);

    auto check = [&](int pn){
        inq.assign(n+1, 0), cnt.assign(n+1, 0), dis.assign(n+1, -inf);
        for(int i=0; i<=n; i++) gra[i].clear(); // [0, n+1]

        for(auto [l, r, c] : q1){
            gra[l-1].push_back({r, c});
        }
        for(auto [l, r, c] : q2){
            gra[r].push_back({l-1, c-pn});
        }
        for(int i=1; i<=n; i++){
            gra[i-1].push_back({i, 0}); // 0 <= pi - pi-1 <= 1 // 两者都要
            gra[i].push_back({i-1, -1});
        }

        queue<int> q;
        for(int i=0; i<=n; i++) q.push(i), inq[i] = true; // 保证所有的限制边都遍历到
        dis[0] = 0, dis[n] = pn; // 设定 p0 = 0 // 二分了 pn , 这里要保持一致
        while(!q.empty()){
            int u = q.front(); q.pop();
            inq[u] = false;
            
            // while 中直接剪枝
            if(u == 0 && dis[u] > 0) return false;
            if(u == n && dis[u] > pn) return false;

            for(auto [v, w] : gra[u]){
                if(dis[u] + w > dis[v]){
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;

                    if(!inq[v]) q.push(v), inq[v] = true;

                    if(cnt[v] >= n+1) return false; // 因为是 n+1 个点啊
                }
            }
        }
        return true;
    };
    
    int lo = -1, hi = n+1;
    while(lo + 1 != hi){
        int mid = lo + hi >> 1;
        if(check(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

此外：，也可以转化成差分约束系统，两边取 log  即可

此篇完结.