「一本通 3.4 练习 1」糖果

形式化题目

给定 $N$ 个正整数变量 $x_1, x_2, \dots, x_N$ （满足 $x_i \geqslant 1$ ）以及 $K$ 个形如 $x_A = x_B$ 、 $x_A < x_B$ 、 $x_A \geqslant x_B$ 、 $x_A > x_B$ 或 $x_A \leqslant x_B$ 的不等式约束。

求满足所有条件的 $\sum_{i=1}^N x_i$ 的最小值；若无解则输出 $-1$ 。

正解

思路

本题要求求出一组未知数满足若干大小关系，且使总和最小。因为每个未知数都要取到满足条件的最小值（下界），我们可以将其建模为差分约束系统。

在差分约束系统中：

如果要计算每个变量的最小值，需将所有约束统一变形为形如 $x_v \geqslant x_u + w$ 的下界形式。
该不等式等价于从顶点 $u$ 向顶点 $v$ 引一条权值为 $w$ 的有向边，在图上求单源最长路。
若图中存在正权回路，则意味着某些变量必须严格大于自身，存在自相矛盾，系统无解（输出 $-1$ ）。

1. 约束条件建图

根据题目给出的 5 类条件进行转化：

$X=1$ ： $x_A = x_B \iff x_A \geqslant x_B + 0$ 且 $x_B \geqslant x_A + 0$ ，故连双向边 $A \xrightarrow{0} B$ 与 $B \xrightarrow{0} A$ 。
$X=2$ ： $x_A < x_B \iff x_B \geqslant x_A + 1$ 。特别地，若 $A = B$ ，自相矛盾直接无解；否则连边 $A \xrightarrow{1} B$ 。
$X=3$ ： $x_A \geqslant x_B \iff x_A \geqslant x_B + 0$ ，连边 $B \xrightarrow{0} A$ 。
$X=4$ ： $x_A > x_B \iff x_A \geqslant x_B + 1$ 。特别地，若 $A = B$ ，直接无解；否则连边 $B \xrightarrow{1} A$ 。
$X=5$ ： $x_A \leqslant x_B \iff x_B \geqslant x_A + 0$ ，连边 $A \xrightarrow{0} B$ 。

此外，每个小朋友都必须分到糖果，即 $x_i \geqslant 1$ 。我们设立超级源点 $0$ （初值设为 $0$ ），向所有点连边：

x_i \geqslant x_0 + 1 \quad (0 \xrightarrow{1} i, \; 1 \leqslant i \leqslant N)

graph LR
    0((0)) -->|1| A((A))
    0((0)) -->|1| B((B))
    A -->|1| B

2. 最长路与正环检测

从超级源点 $0$ 出发运行 SPFA 最长路算法：

松弛条件：若 $dist[v] < dist[u] + w$ ，则更新 $dist[v] = dist[u] + w$ 。
正环检测：记录每个点在最长路路径上的入队或更新次数 $cnt[v]$ 。总点数为 $N+1$ ，若 $cnt[v] > N$ ，说明路径上包含了重复顶点，存在正权环，无解输出 $-1$ 。
实现细节：差分约束判环时，使用后进先出栈（LIFO）代替普通先进先出队列，可以在有环时迅速深入环中反复松弛，极大加快正环的检测速度。

代码

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#!/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-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from collections import deque


def longest_path(n: int, adj: list[list[tuple[int, int]]]) -> int | None:
    """求差分约束系统的最长路总和；若存在正权环则返回 None。"""
    dist = [0] * (n + 1)
    cnt = [0] * (n + 1)
    in_q = [False] * (n + 1)

    # 优先用栈（LIFO）检测正环，对差分约束卡常和判环极快
    stack = list(range(n, -1, -1))
    for u in stack:
        in_q[u] = True

    while stack:
        u = stack.pop()
        in_q[u] = False
        du = dist[u]

        for v, w in adj[u]:
            if dist[v] < du + w:
                dist[v] = du + w
                cnt[v] = cnt[u] + 1
                if cnt[v] > n:
                    return None
                if not in_q[v]:
                    stack.append(v)
                    in_q[v] = True

    return sum(dist[1:])


def solve() -> None:
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    it = iter(input_data)
    n = int(next(it))
    k = int(next(it))

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]

    for _ in range(k):
        x = int(next(it))
        a = int(next(it))
        b = int(next(it))
        if x == 1:
            adj[a].append((b, 0))
            adj[b].append((a, 0))
        elif x == 2:
            if a == b:
                print(-1)
                return
            adj[a].append((b, 1))
        elif x == 3:
            adj[b].append((a, 0))
        elif x == 4:
            if a == b:
                print(-1)
                return
            adj[b].append((a, 1))
        elif x == 5:
            adj[a].append((b, 0))

    # 超级源点 0：每个人至少分 1 个糖果，即 dist[i] >= dist[0] + 1
    # 倒序加边让栈先访问 1..n
    for i in range(n, 0, -1):
        adj[0].append((i, 1))

    total = longest_path(n, adj)
    print(-1 if total is None else total)


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/**
 * 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:32
 * update_at: 2026-10-05 05:32
 */

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

const int MAXN = 100005; // 小朋友数上限
const int MAXM = 700005; // 边数上限：K 条约束最多 2K 条边 + 超级源点 N 条边

typedef long long ll;

int n, k;
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt; // 链式前向星
ll weight[MAXM]; // 边权：不等式右边的常数
ll dist_arr[MAXN]; // dist_arr[v] = x_v 的最小值（最长路距离）
int cnt[MAXN]; // cnt[v] = v 被松弛的次数，用来检测正环
bool in_stack[MAXN]; // v 是否在栈里
int stk[MAXN]; // 手写栈：后进先出，比队列更快检测出正环
ll top_p; // 栈顶指针

// 加一条 u -> v、权为 w 的边，含义是 x_v >= x_u + 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;
}

void read_input() {
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int x, a, b;
        cin >> x >> a >> b;
        if (x == 1) {
            // x_A = x_B：双向 0 边
            add_edge(a, b, 0);
            add_edge(b, a, 0);
        }
        else if (x == 2) {
            // x_A < x_B，即 x_B >= x_A + 1；A = B 时自相矛盾，靠正环判无解
            add_edge(a, b, 1);
        }
        else if (x == 3) {
            // x_A >= x_B，即 x_A >= x_B + 0
            add_edge(b, a, 0);
        }
        else if (x == 4) {
            // x_A > x_B，即 x_A >= x_B + 1
            add_edge(b, a, 1);
        }
        else {
            // x_A <= x_B，即 x_B >= x_A + 0
            add_edge(a, b, 0);
        }
    }
    // 超级源点 0：每个小朋友至少 1 颗糖果，即 x_i >= x_0 + 1
    for (int i = 1; i <= n; i++) {
        add_edge(0, i, 1);
    }
}

// 从超级源点 0 跑最长路；返回糖果总和，存在正环（无解）时返回 -1。
ll solve() {
    // 距离初始化为 0（x_0 = 0），所有点先入栈
    top_p = 0;
    for (int i = 0; i <= n; i++) {
        dist_arr[i] = 0;
        cnt[i] = 0;
        in_stack[i] = true;
        top_p++;
        stk[top_p] = i;
    }

    while (top_p > 0) {
        int u = stk[top_p];
        top_p--;
        in_stack[u] = false;
        ll du = dist_arr[u];
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (dist_arr[v] < du + weight[i]) {
                dist_arr[v] = du + weight[i];
                cnt[v] = cnt[u] + 1; // 借助路径长度判正环
                if (cnt[v] > n) return -1;
                if (!in_stack[v]) {
                    top_p++;
                    stk[top_p] = v;
                    in_stack[v] = true;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dist_arr[i];
    }
    return ans;
}

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

    read_input();
    cout << solve() << endl;

    return 0;
}

复杂度

时间复杂度： $O(N + K)$ 至最坏 $O(N \cdot K)$ 。采用栈优化的 SPFA 实际运行速度极快。
空间复杂度： $O(N + K)$ ，用于存储邻接表、距离数组以及入队标记。

总结

本题是差分约束系统的标准应用题。核心要点在于：

求变量的极小值总和，需将约束条件统一转化为 $x_v \geqslant x_u + w$ 的形式，在图上求解最长路。
建立虚拟超级源点统一所有变量的绝对下界（每个小朋友至少分配 $1$ 颗糖果）。
严格注意严格不等式中 $A=B$ 的非法特判，以及利用栈结构优化 SPFA 的正环检测效率。

「一本通 3.4 练习 1」糖果

目录

形式化题目

正解

思路

1. 约束条件建图

2. 最长路与正环检测

代码

复杂度

总结