【模板】差分约束

题意

为一组

x_c - x_{c'} \le y

形式的不等式求任意可行解，或判断无解。约束只比较两个变量的差，所以对一组解整体加减同一个常数仍然合法，答案不唯一。

思路

不等式等价于 $x_c \le x_{c'} + y$ ，把它读成一条边 $c' \to c$ 、权 $y$ 。于是本题要求的其实就是一组数 $\text{dis}$ ，使每条边都满足

\text{dis}[v] \le \text{dis}[u] + w

注意 $\text{dis}$ 在这里不是“某个源点到 $u$ 的最短路”，它就是待求的 $x_u$ 本身；判定标准里没有源点，只有边。

初值可以随便取

约束只比较差值，把一组解整体加同一个常数仍然合法，所以解有无穷多组。松弛做的事是：只要某条边违反 $x_v \le x_u + w$ ，就把 $x_v$ 改小到 $x_u + w$ ，然后重复，直到改不动为止。

因此初值只决定最后落在解集的哪个位置，不影响合法性。同一组样例换初值，收敛到的解整体平移，但都合法：

初值	收敛结果
$(0,0,0)$	$(0,-2,0)$
$(5,5,5)$	$(5,3,5)$
$(1,2,3)$	$(1,1,3)$

唯一的限制是初值必须有限：INF 表示“还没决定”，保持 INF 的点根本不会被比较，输出就是无效的。所以最省事的做法是全部置 $0$ 。

为什么是所有点入队，而不是挑一个起点

把每个点的初值取 $0$ 并全部入队，等价于加一个到所有点都是 $0$ 权边的超级源点，只是省掉了那个虚拟点。

不能只挑一个点出发。例如约束 $x_2 - x_1 \le -5$ 对应边 $1 \to 2$ 、权 $-5$ ：

从 $1$ 号点出发，能松弛到 $2$ ，得到 0 -5，合法；
只从 $2$ 号点出发， $1$ 号点收不到任何松弛，输出 0 0，而 $x_2 - x_1 = 0 > -5$ ，不合法。

所以“每个弱连通块挑一个点”也不行：弱连通不等于有向可达，边方向一旦反过来，挑中的起点就到不了另一端。全部入队对任何边方向都成立。

队列空就等于全部满足

松弛只会让 $\text{dis}$ 变小，从不增大。队列为空意味着每个点都“最后被扫过一次”，且那次扫描时它的所有出边都不可改善；此后它的值也不会再变。于是每条边都在起点的终值下被验证过，终态必然满足全部约束。

反过来，如果存在负环，沿环可以无限把值改小，队列永远清不空。实现上用“最短路径边数达到 $n$ ”来检测：走得比 $n-1$ 条还多，路径上必然绕出了负环。此时约束自相矛盾，输出 NO；否则 $\text{dis}[1..n]$ 就是答案。

建边方向

题面写法	归一为 $\le$	建边
$x_c - x_{c'} \le y$	不变	$c' \to c$ 权 $y$
$x_c - x_{c'} \ge y$	$x_{c'} - x_c \le -y$	$c \to c'$ 权 $-y$
$x_c = x_{c'}$	两个方向各一条 $0$ 权边	$c \to c'$ 与 $c' \to c$ 权 $0$

本题只有第一种，直接调用 add_leq(c', c, y) 即可。

代码

C++ 版基于 rbook 代码模板 diff-constraints（见文章差分约束：把不等式组变成最短路）：add_leq 统一不等式方向，feasible() 做全局可行性检查并留下可行解。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-10-20 09:10
 */
// 差分约束：把 x_c - x_c' <= y 变成边 c' -> c 权 y，
// 所有点距离初始为 0（等价于超级源向每个点连 0 权边）跑 SPFA 求任意一组可行解。
// 没有负环时 dis 就是可行解；出现负环说明约束自相矛盾，输出 NO。
// 模板来源：rbook 代码模板 diff-constraints（差分约束的建边、全局可行性与单源最短路）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e3 + 5;

struct Edge {
    int to;
    ll w;
};

int n, m;
vector<Edge> g[maxn];   // g[u]：从 u 出发的边，边 u -> v 权 w 代表 x_v - x_u <= w
ll dis[maxn];           // feasible() 之后是一组可行解
int cnt[maxn];          // 当前 dis 对应的路径边数，达到 n 说明绕出了负环
bool in_queue[maxn];

// 全局可行性：所有点距离取 0 并全部入队，等价于加一个到所有点都是 0 权边的超级源点。
// 返回 false 表示存在负环、约束无解；返回 true 时 dis[1..n] 就是一组可行解。
bool feasible() {
    fill(dis, dis + n + 1, 0);
    fill(cnt, cnt + n + 1, 0);
    fill(in_queue, in_queue + n + 1, true);
    queue<int> q;
    for (int u = 1; u <= n; ++u) q.push(u);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (const Edge &e : g[u]) {
            if (dis[u] + e.w >= dis[e.to]) continue;  // 这条边给不出更紧的上界
            dis[e.to] = dis[u] + e.w;
            cnt[e.to] = cnt[u] + 1;
            if (cnt[e.to] >= n) return false;         // 更短的路用了至少 n 条边，必然有负环
            if (!in_queue[e.to]) {
                q.push(e.to);
                in_queue[e.to] = true;
            }
        }
    }
    return true;
}

void read_data() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int c, c2;
        ll y;
        cin >> c >> c2 >> y;
        // x_c - x_c' <= y  <=>  x_c <= x_c' + y，于是建边 c' -> c 权 y
        g[c2].push_back({c, y});
    }
}

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

    if (!feasible()) {
        cout << "NO\n";
        return 0;
    }
    for (int i = 1; i <= n; ++i) cout << dis[i] << " \n"[i == n];

    return 0;
}

Python 版不再包成类，只保留一个 find_solution()：返回解，或有负环时返回 None。接口变短了但算法完全相同——初值全 0、全点入队、路径边数判负环。

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-20 09:46

import sys
from collections import deque

type WeightedAdj = list[list[tuple[int, int]]]  # graph[u]：若干 (终点 v, 边权 w)


def find_solution(graph: WeightedAdj, n: int) -> list[int] | None:
    """返回一组满足全部约束的解；约束自相矛盾（有负环）时返回 None。

    所有点距离取 0 并全部入队，等价于加一个到每个点都是 0 权边的超级源点：
    初值只是假定值，整体平移不影响合法性，所以取 0 最省事。
    用路径边数判负环：更短的路走了至少 n 条边，路径上必然绕出了负环。
    """
    dis = [0] * (n + 1)
    path_len = [0] * (n + 1)  # 当前 dis 对应的路径边数
    in_queue = [True] * (n + 1)
    q = deque(range(1, n + 1))

    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            shorter = dis[u] + w
            if shorter >= dis[v]:
                continue  # 这条边给不出更紧的上界
            dis[v] = shorter
            path_len[v] = path_len[u] + 1
            if path_len[v] >= n:
                return None
            if not in_queue[v]:
                q.append(v)
                in_queue[v] = True

    return dis[1:]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    graph: WeightedAdj = [[] for _ in range(n + 1)]
    for _ in range(m):
        c, c2, y = next(data), next(data), next(data)
        graph[c2].append((c, y))  # x_c - x_c' <= y  <=>  x_c <= x_c' + y，建边 c' -> c 权 y

    ans = find_solution(graph, n)
    print("NO" if ans is None else " ".join(map(str, ans)))


if __name__ == "__main__":
    solve()

复杂度

find_solution() 只跑一次 SPFA，最坏 $O(nm)$ ，空间 $O(n+m)$ 。本题 $n,m \le 5 \times 10^3$ ，足够。

Python 知识

type WeightedAdj = list[list[tuple[int, int]]] 给邻接表起别名，读的时候不用反复展开嵌套泛型。
deque(range(1, n+1)) 一次把所有点按编号入队，正好是“超级源连 0 权边”的初始状态。
next(data) 顺序消费读入，每行的三个值直接取用，不用手算 2 + 3*i 偏移。
path_len 和 dis 一起在松弛时更新，负环判定就成了一行 if path_len[v] >= n。
返回值用 list[int] | None 而不是另设布尔标记，None 自带“无解”含义，主流程一句 print("NO" if ans is None else ...) 就分完了。

对拍

gen.py 一半生成随机边（容易造出负环），一半先取一组真解再反推边权（保证有解）；brute.cpp 直接枚举 $x_i$ 取值并检查约束，用来自动核对 main.cpp 与 main.py 的输出是否满足全部不等式。

总结

差分约束的建边方向来自把不等式写成一次松弛公式： $x_v \le x_u + w$ 对应 $u \to v$ 权 $w$ 。跑最短路得到的是所有差值上界里最紧的那一组，它同时是解；负环则是"上界可以无限收缩"的表现，即无解。