差分约束

概念讲解

什么是差分约束？

差分约束是将不等式组转化为图论最短/最长路问题的技巧。

核心思想

对于不等式 x_j - x_i <= c，可以转化为从 i 到 j 的边权为 c。

实现

建图

1234// x_j - x_i <= c 建边 i -> j 权值为 c
void addEdge(int i, int j, int c) {
    graph[i].push_back({j, c});
}

求解

使用 SPFA 求最短路或最长路。

1234567891011121314151617181920212223242526272829303132333435bool spfa(int n) {
    vector<int> dist(n + 1, 1e9);
    vector<int> count(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    // 添加超级源点
    for (int i = 1; i <= n; i++) {
        q.push(i);
        inQueue[i] = true;
        dist[i] = 0;
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    if (count[v] > n) return false; // 有负环
                }
            }
        }
    }
    
    return true;
}

考点分析

初赛考查方式

选择题： 差分约束的概念
程序阅读： 理解差分约束
编程题： 差分约束应用

常见题型

不等式组求解
最大/最小值

例题精讲

例题 1：差分约束

题目： 求解不等式组。

解答：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    
    // SPFA 求解
    vector<int> dist(n + 1, 1e9);
    vector<int> count(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        q.push(i);
        inQueue[i] = true;
        dist[i] = 0;
    }
    
    bool hasNegativeCycle = false;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    if (count[v] > n) {
                        hasNegativeCycle = true;
                        break;
                    }
                }
            }
        }
        
        if (hasNegativeCycle) break;
    }
    
    if (hasNegativeCycle) {
        cout << "无解" << endl;
    } else {
        for (int i = 1; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

练习题

洛谷 P1993 小 K 的农场

查看答案

思路：差分约束，将不等式转化为图论问题。

x - y >= c → y -> x 权值为 -c
x - y <= c → x -> y 权值为 c
x == y → 两条边

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int,int>>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        
        if (op == 1) {
            // a - b >= c
            int c;
            cin >> c;
            graph[b].push_back({a, c});
        } else if (op == 2) {
            // a - b <= c
            int c;
            cin >> c;
            graph[a].push_back({b, -c});
        } else {
            // a == b
            graph[a].push_back({b, 0});
            graph[b].push_back({a, 0});
        }
    }
    
    // SPFA
    vector<int> dist(n + 1, 0);
    vector<int> count(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        q.push(i);
        inQueue[i] = true;
    }
    
    bool hasNegativeCycle = false;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w > dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    if (count[v] > n) {
                        hasNegativeCycle = true;
                        break;
                    }
                }
            }
        }
        
        if (hasNegativeCycle) break;
    }
    
    cout << (hasNegativeCycle ? "No" : "Yes") << endl;
    return 0;
}

洛谷 P3275 [SCOI2011] 糖果

查看答案

思路：差分约束，注意要跑最长路。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int,int>>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        
        if (op == 1) {
            graph[a].push_back({b, 0});
            graph[b].push_back({a, 0});
        } else if (op == 2) {
            graph[a].push_back({b, 1});
        } else if (op == 3) {
            graph[b].push_back({a, 0});
        } else if (op == 4) {
            graph[b].push_back({a, 1});
        } else {
            graph[a].push_back({b, 0});
        }
    }
    
    // 添加超级源点
    for (int i = 1; i <= n; i++) {
        graph[0].push_back({i, 1});
    }
    
    // SPFA 最长路
    vector<int> dist(n + 1, -1e9);
    vector<int> count(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    q.push(0);
    inQueue[0] = true;
    dist[0] = 0;
    
    bool hasPositiveCycle = false;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w > dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    if (count[v] > n) {
                        hasPositiveCycle = true;
                        break;
                    }
                }
            }
        }
        
        if (hasPositiveCycle) break;
    }
    
    if (hasPositiveCycle) {
        cout << -1 << endl;
    } else {
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dist[i];
        }
        cout << ans << endl;
    }
    
    return 0;
}

洛谷 P5960 差分约束模板

查看答案

思路：差分约束模板题，求解不等式组的最小值。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int,int>>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[b].push_back({a, c});
    }
    
    // 添加超级源点
    for (int i = 1; i <= n; i++) {
        graph[0].push_back({i, 0});
    }
    
    // SPFA 最短路
    vector<int> dist(n + 1, 1e9);
    vector<int> count(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    q.push(0);
    inQueue[0] = true;
    dist[0] = 0;
    
    bool hasNegativeCycle = false;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    if (count[v] > n) {
                        hasNegativeCycle = true;
                        break;
                    }
                }
            }
        }
        
        if (hasNegativeCycle) break;
    }
    
    if (hasNegativeCycle) {
        cout << "NO" << endl;
    } else {
        for (int i = 1; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

易错点

⚠️ 注意：

差分约束要转化为最短/最长路

注意负环的判断

要添加超级源点

差分约束是图论的高级应用

差分约束

概念讲解

什么是差分约束？

核心思想

实现

建图

求解

考点分析

初赛考查方式

常见题型

例题精讲

例题 1：差分约束

练习题

易错点

练习完成

恭喜完成学习！

提示

题目反馈