【模板】差分约束

题意

为一组 x_c-x_c'<=y 不等式求任意可行解，或判断无解。

思路

不等式等价于 x_c <= x_c' + y，建边 c' -> c 权 y。所有距离初始为 0 相当于超级源向每点连 0 边；若出现负环则无解，否则最终距离就是一组可行解。

Python 知识

deque(range(1,n+1)) 一次把所有点加入超级源队列。
bytearray(b"\x01")*(n+1) 紧凑初始化入队标记。
Python 条件表达式直接选择输出解或 NO。

代码

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
31import sys
from collections import deque


input = sys.stdin.buffer.readline
n, constraints = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(constraints):
    left, right, limit = map(int, input().split())
    graph[right].append((left, limit))

distance = [0] * (n + 1)
edge_count = [0] * (n + 1)
in_queue = bytearray(b"\x01") * (n + 1)
queue = deque(range(1, n + 1))
possible = True
while queue and possible:
    node = queue.popleft()
    in_queue[node] = 0
    for neighbor, weight in graph[node]:
        candidate = distance[node] + weight
        if candidate < distance[neighbor]:
            distance[neighbor] = candidate
            edge_count[neighbor] = edge_count[node] + 1
            if edge_count[neighbor] >= n:
                possible = False
                break
            if not in_queue[neighbor]:
                queue.append(neighbor)
                in_queue[neighbor] = 1
print(*distance[1:]) if possible else print("NO")

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

SPFA 最坏 O(nm)，空间 O(n+m)。

总结

差分约束的建边方向来自把不等式写成一次松弛公式。

【模板】差分约束

目录

题意

思路

Python 知识

代码

复杂度

总结