差分约束

HeJie2026-08-272026-09-17

差分约束系统 是一种特殊的元一次不等式组，它包含个变量，以及个约束条件，每个条件是有两个变量做差构成的，形如 . 我们要解决的问题是：求一组解，使得所有的约束条件得到满足，否则判断出无解.

1. 变形

差分约束系统中的每个约束条件：都可以变形成：

2. 转化

接下来，思考一个图论的问题。

dist[i] 是从起点到地的最短距离
dist[j] 是从起点到地的最短距离
是从地到地的路线长度（边权）

则是必然的，否则 dist[i] 就不是最短的距离。

所以，在最短路算法中，其本质工作就是检查所有的边，确保图中所有的边都满足这个条件。

到这里，我们发现这两个式子格式完全一样，但是虽然两者代数关系相同，但是想直接关联起来还是比较抽象。

我们不妨画一张这样的图，虚构一个不存在的“起点”，连一条虚边指向，边权为最短路 dist[i] 的值。

于是，根据单源最短路的定义，我们轻易知道，最短路不成立的情况就是有负环的情况。

所以对于不等式：可以连接从到的一条边，连接所有不等式构成的边，构建出最后的图。

3. 实现

可以用 SPFA 来判断图中是否出现负环，具体的做法是：开一个 cnt 数组记录最短路径上边的个数，当成功松弛操作之后，即若，让。当最短路边的个数大于等于所有点的个数时，说明出现了负环。

同时，在构建一条有向边的过程，其意义就是是指起点（弧头）对终点（弧尾）提出要求，要求终点的值不能大于某个值，所以最后得到的就是一个极大值。

同理，我们也可以用最长路的方式建图，也就是对于一个不等式，则连一条边从指向，并在最后做最长路的 SPFA。

例题1：【模板】差分约束

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 2>>> adj(n + 1);
    
    int u, v, w;
    while (m --) {
        cin >> u >> v >> w;
        adj[v].push_back({u, w});
    }

    queue<int> q;
    vector<int> d(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; i ++) q.push(i);

    while (q.size()) {
        auto u = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (d[v] > d[u] + w) {
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) {
                    cout << "NO\n";
                    return 0;
                }
                q.push(v);
                d[v] = d[u] + w;
            }
        }
    }

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

    return 0;
}

例题2: CF2245D2

可以用差分约束的方式处理两个不等式：

转化为

转化为

我们发现，其中不仅涉及了一个点本身，还涉及了其负数形式，所以我们用拆点的方法，将一个点拆为两个点，分别表示和。在构建图的时候，需要同时为两个点添加边，从而确保逻辑完整，所以，不等式转化为：

转化为和

转化为和

于是，我们得到了一个图，首先判断有没有负权环，由于 SPFA 的时间复杂度是，所以显然会超时。观察图的性质，发现边权只有和两种，而如果成环，在图中一定会构成强连通分量，所以这道题目中，在强连通分量中，当且仅当包含了一个边权为的边时，图中存在负权环。

先用 tarjan 进行缩点，看每个 SCC 中有没有负权边，就可以判断是否可行。

然后，tarjan 算法处理后的图，得到了拓扑序的一个 DAG，用 dp 来得到最短路即可。根据这个限定的最大值，可以得到每个点的最大值，通过这个限定的范围，取一个值就是答案。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    int num_nodes = 2 * n;
    // node 1 to n correspond to x_i
    // node n+1 to 2n correspond to y_i (which is -x_i)
    vector<vector<pair<int, int>>> adj(num_nodes + 1);
    
    struct Edge {
        int u, v, w;
    };
    vector<Edge> edges;

    for (int k = 0; k < m; ++k) {
        int o, i, j;
        cin >> o >> i >> j;
        if (o == 1) {
            // y_j -> x_i (weight 0), y_i -> x_j (weight 0)
            int u1 = j + n, v1 = i;
            int u2 = i + n, v2 = j;
            adj[u1].push_back({v1, 0});
            adj[u2].push_back({v2, 0});
            edges.push_back({u1, v1, 0});
            edges.push_back({u2, v2, 0});
        } else {
            // x_i -> y_j (weight 1), x_j -> y_i (weight 1)
            int u1 = i, v1 = j + n;
            int u2 = j, v2 = i + n;
            adj[u1].push_back({v1, 1});
            adj[u2].push_back({v2, 1});
            edges.push_back({u1, v1, 1});
            edges.push_back({u2, v2, 1});
        }
    }

    vector<int> dfn(num_nodes + 1, 0), low(num_nodes + 1, 0), scc(num_nodes + 1, 0);
    vector<int> st;
    vector<bool> in_st(num_nodes + 1, false);
    int timer = 0, scc_cnt = 0;

    auto tarjan = [&](auto& self, int u) -> void {
        dfn[u] = low[u] = ++timer;
        st.push_back(u);
        in_st[u] = true;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            if (!dfn[v]) {
                self(self, v);
                low[u] = min(low[u], low[v]);
            } else if (in_st[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if (low[u] == dfn[u]) {
            ++scc_cnt;
            while (true) {
                int v = st.back();
                st.pop_back();
                in_st[v] = false;
                scc[v] = scc_cnt;
                if (u == v) break;
            }
        }
    };

    for (int i = 1; i <= num_nodes; ++i) {
        if (!dfn[i]) {
            tarjan(tarjan, i);
        }
    }

    for (const auto& e : edges) {
        if (e.w == 1 && scc[e.u] == scc[e.v]) {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
    for (int i = 1; i <= n; ++i) {
        // tarjan outputs SCCs in reverse topological order,
        // so `scc_cnt - scc[i]` functions as a strict topological order layout.
        int topo_xi = scc_cnt - scc[i];
        int topo_yi = scc_cnt - scc[i + n];
        cout << topo_xi - topo_yi << (i == n ? "" : " ");
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}