「一本通 3.4 练习 2」排队布局

形式化题目

给定 $N$ 个实数变量 $x_1, x_2, \dots, x_N$ ，满足以下三种不等式约束：

顺序约束：对于所有 $1 \le i < N$ ，满足 $x_i \le x_{i+1}$ ；
上限约束：给出 $M_L$ 条限制，每条指定两个变量 $A, B$ （不妨设 $A < B$ ），满足 $x_B - x_A \le D$ ；
下限约束：给出 $M_D$ 条限制，每条指定两个变量 $A, B$ （不妨设 $A < B$ ），满足 $x_B - x_A \ge D$ 。

求：

若该不等式系统无可行解，输出 -1；
若在满足所有约束的情况下， $x_N - x_1$ 可以任意大，输出 -2；
否则输出 $x_N - x_1$ 的最大可能值。

正解

思路

本题求变量差值的最大值，且所有约束均为形如 $x_v - x_u \le w$ 的两元一次差分不等式，这是标准的差分约束系统。

1. 建图转换

在单源最短路中，三角形不等式为：

dist[v] \le dist[u] + w

变形后即为：

dist[v] - dist[u] \le w

因此，每个不等式 $x_v - x_u \le w$ 都可以转化为一条从节点 $u$ 指向节点 $v$ 、权值为 $w$ 的有向边：

顺序约束： $x_i \le x_{i+1} \iff x_i - x_{i+1} \le 0$ ，从节点 $i+1$ 向节点 $i$ 连一条边权为 $0$ 的边。
好感限制： $x_B - x_A \le D$ （保证 $A < B$ ），从节点 $A$ 向节点 $B$ 连一条边权为 $D$ 的边。
反感限制： $x_B - x_A \ge D \iff x_A - x_B \le -D$ （保证 $A < B$ ），从节点 $B$ 向节点 $A$ 连一条边权为 $-D$ 的边。

2. 两阶段 SPFA 判定与求解

因为图可能存在多个不连通的分量，且 $1$ 号节点不一定能到达所有节点，需要分为两个阶段处理：

第一阶段（全局负环检测）：若整个不等式组中存在相互矛盾（即图中存在负权环），则无解。为了检测整张图中是否存在负权环，引入超级源点（或初始化时将所有节点 $1 \sim N$ 的初始距离设为 $0$ 并全部推入队列），运行一次 SPFA。若有任意节点入队次数达到 $N$ ，说明存在负权环，直接输出 -1。
第二阶段（求最大距离）：在排除负环后，以 $1$ 号节点为单源起点（令 $dist[1] = 0$ ，其余为 $+\infty$ ）运行 SPFA。
- 若 $dist[N] = +\infty$ ，说明从 $1$ 出发无法到达 $N$ ， $x_N - x_1$ 不受任何上界路径约束，可以任意大，输出 -2；
- 否则， $dist[N]$ 就是在满足所有约束条件下 $x_N - x_1$ 的最大值，输出 $dist[N]$ 。

代码

Python 版：

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
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
86
87
88
89
90
91
92
93#!/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-09-30 15:31
# update_at: 2026-09-30 15:31

import sys
from collections import deque

INF = 10**18


def spfa(n: int, adj: list[list[tuple[int, int]]], source: int | None) -> tuple[bool, list[int]]:
    """用 SPFA 求从源点出发的最短路并检测负环。

    若 source 为 None，则初始将所有点入队（等价于建立超级源点向各点连边权 0 的边），
    用于全局判负环。
    返回 (has_negative_cycle, dist)。
    """
    dist = [0 if source is None else INF] * (n + 1)
    in_queue = [True if source is None else False] * (n + 1)
    count = [0] * (n + 1)
    queue = deque(range(1, n + 1) if source is None else [source])

    if source is not None:
        dist[source] = 0
        in_queue[source] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False
        d_u = dist[u]

        for v, w in adj[u]:
            cand = d_u + w
            if cand < dist[v]:
                dist[v] = cand
                if not in_queue[v]:
                    count[v] += 1
                    if count[v] >= n:
                        return True, dist
                    in_queue[v] = True
                    queue.append(v)

    return False, dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    tokens = list(data)
    if not tokens:
        return
    it = iter(tokens)
    n, ml, md = next(it), next(it), next(it)

    # 建图：adj[u] 存储出边 (v, w)，表示不等式 dist[v] <= dist[u] + w
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]

    # 1. 相对顺序限制：x[i] <= x[i+1] => x[i] - x[i+1] <= 0 => 从 i+1 到 i 连边权 0
    for i in range(1, n):
        adj[i + 1].append((i, 0))

    # 2. 友好关系：x[b] - x[a] <= d (a < b) => 从 a 到 b 连边权 d
    for _ in range(ml):
        a, b, d = next(it), next(it), next(it)
        if a > b:
            a, b = b, a
        adj[a].append((b, d))

    # 3. 反感关系：x[b] - x[a] >= d (a < b) => x[a] - x[b] <= -d => 从 b 到 a 连边权 -d
    for _ in range(md):
        a, b, d = next(it), next(it), next(it)
        if a > b:
            a, b = b, a
        adj[b].append((a, -d))

    # 第一阶段：全局负环检测（无解判定）
    has_neg_cycle, _ = spfa(n, adj, None)
    if has_neg_cycle:
        print(-1)
        return

    # 第二阶段：以 1 号牛为起点求单源最短路
    _, dist = spfa(n, adj, 1)
    if dist[n] == INF:
        print(-2)
    else:
        print(dist[n])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * 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-10-05 05:37
 * update_at: 2026-10-05 05:37
 */
// 排队布局：差分约束 + SPFA
// 设 x[i] 为第 i 头牛的坐标，三类约束统一写成 x[v] - x[u] <= w，从 u 向 v 连一条权为 w 的有向边：
//   顺序约束：x[i] <= x[i+1]，即 x[i] - x[i+1] <= 0，从 i+1 向 i 连权 0；
//   好感约束：x[b] - x[a] <= d，从 a 向 b 连权 d；
//   反感约束：x[b] - x[a] >= d，即 x[a] - x[b] <= -d，从 b 向 a 连权 -d。
// 先让所有点初值为 0 全部入队跑一次 SPFA 判全局负环：有负环则无解，输出 -1；
// 再以 1 号牛为源跑最短路：到不了 n 号牛说明距离可任意大，输出 -2，否则 dist[n] 就是最大距离。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;   // 节点数上限 N <= 1000
const int MAXM = 30005;  // 边数上限 (N-1) + M_L + M_D <= 20999
const ll INF = 1000000000000000000LL;  // 无穷大，不用 LLONG_MAX 以免加法溢出

// 链式前向星存图，边的含义是 x[to] - x[u] <= weight
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
ll weight[MAXM];  // 边权可能为负，必须用 ll

ll dist[MAXN];        // 单源最短路距离
bool in_queue[MAXN];  // 节点当前是否在队列中
int push_cnt[MAXN];   // 节点因松弛而入队的次数，达到 n 次说明存在负环

int n, ml, md;

// 加一条 u -> v、权 w 的有向边。
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// SPFA：source == 0 表示全局判负环（所有点初值 0 并一起入队，等价于建超级源点），
// 否则以 source 为源点求最短路。返回 true 表示图中存在负环。
bool spfa(int source) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        in_queue[i] = false;
        push_cnt[i] = 0;
        if (source == 0) {
            dist[i] = 0;  // 全局判环时所有点都是源点
            in_queue[i] = true;
            q.push(i);
        } else {
            dist[i] = INF;
        }
    }
    if (source != 0) {
        dist[source] = 0;
        in_queue[source] = true;
        q.push(source);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (dist[u] + weight[e] < dist[v]) {
                dist[v] = dist[u] + weight[e];
                if (!in_queue[v]) {
                    push_cnt[v]++;
                    if (push_cnt[v] >= n) return true;  // 同一节点入队 n 次，必有负环
                    in_queue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d", &n, &ml, &md);

    for (int i = 1; i < n; i++) {
        add_edge(i + 1, i, 0);
    }
    for (int i = 0; i < ml; i++) {
        int a, b;
        ll d;
        scanf("%d%d%lld", &a, &b, &d);
        if (a > b) swap(a, b);
        add_edge(a, b, d);
    }
    for (int i = 0; i < md; i++) {
        int a, b;
        ll d;
        scanf("%d%d%lld", &a, &b, &d);
        if (a > b) swap(a, b);
        add_edge(b, a, -d);
    }

    if (spfa(0)) {
        printf("-1\n");
        return 0;
    }
    spfa(1);
    if (dist[n] == INF) {
        printf("-2\n");
    } else {
        printf("%lld\n", dist[n]);
    }
    return 0;
}

复杂度

时间复杂度：图中有 $V = N \le 1000$ 个节点， $E = (N - 1) + M_L + M_D \le 21000$ 条边。SPFA 的平均运行时间为 $O(kE)$ （ $k$ 为常数），最坏情况下为 $O(VE)$ 。在本题数据规模下运行耗时通常在 20ms 以内，远低于时限要求。
空间复杂度：存储邻接表、距离数组和队列状态需要 $O(V + E)$ 的额外空间，内存开销在数兆字节级别。

总结

差分约束的核心在于统一不等式方向：

求变量差的最大值时，统一转化为 $x_v - x_u \le w$ 的形式建图求最短路；
判断系统整体可行性时，必须做全局负环检测（全点初始入队）；在系统有解的前提下，再以指定点为单源起点求最短路。

图示解析

以样例输入为例：

$N=4, M_L=2, M_D=1$
好感约束： $x_3 - x_1 \le 10$ ， $x_4 - x_2 \le 20$
反感约束： $x_3 - x_2 \ge 3 \implies x_2 - x_3 \le -3$
顺序约束： $x_1 - x_2 \le 0$ ， $x_2 - x_3 \le 0$ ， $x_3 - x_4 \le 0$

建图后各节点之间的边权关系如下图所示：

graph LR
    1((1))
    2((2))
    3((3))
    4((4))

    1 -- "10" --> 3
    2 -- "20" --> 4
    3 -- "-3" --> 2
    2 -- "0" --> 1
    3 -- "0" --> 2
    4 -- "0" --> 3

计算最短路时：

从 $1$ 到 $3$ 最短路径为 $1 \xrightarrow{10} 3$ ，距离为 $10$ ；
从 $3$ 到 $2$ 边权为 $-3$ ，故 $1$ 到 $2$ 的最短路为 $10 + (-3) = 7$ ；
从 $2$ 到 $4$ 边权为 $20$ ，故 $1$ 到 $4$ 的最短路为 $7 + 20 = 27$ 。
因此 $x_4 - x_1$ 的最大可能值为 $27$ 。

「一本通 3.4 练习 2」排队布局

目录

形式化题目

正解

思路

1. 建图转换

2. 两阶段 SPFA 判定与求解

代码

复杂度

总结

图示解析