[SCOI2011] 糖果

题意

满足五类大小关系且每人至少一颗糖，求最小糖果总数；无解输出 $-1$ 。

思路

统一写成下界

要求“最少”，所以把五类关系全部改写成下界形式 $x_v \ge x_u + w$ ：

题面	原始含义	归一为 $x_v \ge x_u + w$	权值
`1 A B`	$x_A = x_B$	$x_A \ge x_B$ 且 $x_B \ge x_A$	0, 0
`2 A B`	$x_A < x_B$	$x_B \ge x_A + 1$	1
`3 A B`	$x_A \ge x_B$	不变	0
`4 A B`	$x_A > x_B$	$x_A \ge x_B + 1$	1
`5 A B`	$x_A \le x_B$	$x_B \ge x_A$	0

关键是“小于”能写成“至少少 1”：因为糖果数是整数。这一步把所有权值压到了 $\{0, 1\}$ ，后面的一切都建立在这个离散性上。

有了下界约束，最小解就是每条链上最紧的那个：

x_v = \max\Big(1,\ \max_{\text{指向 } v \text{ 的路径}} \text{路径权和}\Big)

初值取 1 是因为每人至少一颗。这就是最长路。

矛盾长什么样

最长路在一般图上会因正环而不收敛。而本题权值只有 0 和 1，所以一个环的权权和恰好等于：

\text{环权和} = \text{环上权 1 边的条数}

于是“存在正环”退化成一个存在性判定：只需看一个环上有没有权 1 边。

但直接在原图上跑 SPFA 判环会 TLE（ $N, K \le 10^5$ ，出题人明确卡了 SPFA）。需要一个线性方法。

为什么矛盾一定在 SCC 内部

这是全题最关键的一步。有向图有个结构定理：

任何有向环都完全包含在某个强连通分量里。

理由：若环跨了多个 SCC，把图缩点后它投影成 DAG 上的一条闭合路径——而 DAG 里不存在环。

所以把图按 SCC 分解后，环的可能性只剩“分量内部”。判定变成：

对每个 SCC，看它的内部边里有没有权 1 的边。有则无解，否则有解。

为什么权 0 边在 SCC 内部无害？ 因为全 0 环的权和为 0，不是正环；它只表示“这些点必须相等”。而权 1 边是“自我抬高”的约束，一旦成环就要求 $x > x$ ，矛盾。

缩点后在 DAG 上 DP

无解排除后，缩点得到一个 DAG。为什么要缩点而不是直接跑最长路？两个原因：

正确性：同一 SCC 内的点被强制相等，必须取同一值。缩点让这件事显式化，避免最长路给同分量的不同点算出不同值。
复杂度：DAG 上按拓扑序做最长路是 $O(n+m)$ ，彻底摆脱 SPFA 最坏的 $O(NK)$ 。

分量 $c$ 的值满足：

val[c] = \max\Big(1,\ \max_{(p,c,w)} \big(val[p] + w\big)\Big)

最后分量内每个点都拿 $val[c]$ 颗，所以总数为：

\text{ans} = \sum_{c} val[c] \cdot |c|

两个容易漏掉的边界

自环：X=2 且 $A = B$ 表示“自己少于自己”，X=4 同理，两者都必矛盾，可以提前拦下。X=1/3/5 的自环是合法的（自己等于/不少于/不多于自己）。
所有点孤立也合法：没有任何约束时每个人拿 1 颗，总数为 $N$ 。所以分量的初值必须是 1 而不是 0。

Python 知识

显式栈实现 Kosaraju 两遍 DFS，避免递归深度问题（ $10^5$ 的链会超出默认递归限制）。
deque 做缩点 DAG 的拓扑排序，入度降为 0 就入队。
分量大小乘分量最长路值，直接得到总糖果数。
possible &= a != b 用位运算的与把“所有自环检查都通过”累积成一个布尔值，不必提前 break。

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169#!/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-21 08:20
#
# main.py：糖果。五类大小关系 + 每人至少一颗，求最小糖果总数。
# 全部写成下界形式 x_v >= x_u + w：
#   X=1 相等     -> 两个方向各一条 0 权边
#   X=2 少于     -> x_b >= x_a + 1（整数性让"少于"就是"至少少 1"）
#   X=3 不少于   -> x_b >= x_a 的反向：x_a >= x_b，权 0
#   X=4 多于     -> x_a >= x_b + 1
#   X=5 不多于   -> x_b >= x_a，权 0
# 要求最少就是求最长路，初值 1（每人至少一颗）。
# 矛盾判定：权值只有 0/1，所以环权和 = 环上权 1 边的条数；而任何有向环都完全落在
# 某个强连通分量内，于是只需检查每个分量内部有没有权 1 边。全 0 环权和为 0，无害。
# 无解排除后缩点成 DAG，按拓扑序做最长路；同分量点强制相等，最后按分量大小加权求和。

import sys
from collections import deque

type Adj = list[list[int]]          # 邻接表，只存终点
type EdgeList = list[tuple[int, int, int]]  # (起点 u, 终点 v, 权 w)，含义 x_v >= x_u + w


def build_graph(n: int, data) -> tuple[Adj, Adj, EdgeList, bool]:
    """返回 (正向图, 反向图, 边表, 是否已判定矛盾)。"""
    graph: Adj = [[] for _ in range(n + 1)]
    reverse_graph: Adj = [[] for _ in range(n + 1)]
    edges: EdgeList = []
    possible = True

    def add_edge(u: int, v: int, w: int) -> None:
        """加一条 u -> v 权 w 的有向边：x_v >= x_u + w。"""
        graph[u].append(v)
        reverse_graph[v].append(u)
        edges.append((u, v, w))

    for _ in range(next(data)):
        kind, a, b = next(data), next(data), next(data)
        if kind == 1:
            add_edge(a, b, 0)   # x_a >= x_b
            add_edge(b, a, 0)   # x_b >= x_a
        elif kind == 2:
            possible &= a != b  # 自己少于自己必矛盾
            add_edge(a, b, 1)   # x_b >= x_a + 1
        elif kind == 3:
            add_edge(b, a, 0)   # x_a >= x_b
        elif kind == 4:
            possible &= a != b  # 自己多于自己必矛盾
            add_edge(b, a, 1)   # x_a >= x_b + 1
        else:
            add_edge(a, b, 0)   # x_a <= x_b 即 x_b >= x_a

    return graph, reverse_graph, edges, possible


def kosaraju(graph: Adj, reverse_graph: Adj, n: int) -> tuple[list[int], int]:
    """两遍 DFS 求强连通分量；返回 (每个点所属分量编号, 分量个数)。

    用显式栈代替递归，避免 n=1e5 的链超出递归深度。
    """
    visited = bytearray(n + 1)
    finish_order: list[int] = []

    # 第一遍：正向图 DFS，记录每个点的结束时间
    for start in range(1, n + 1):
        if visited[start]:
            continue
        visited[start] = 1
        stack = [(start, 0)]  # (点, 下一条要看的出边下标)
        while stack:
            node, index = stack[-1]
            if index < len(graph[node]):
                neighbor = graph[node][index]
                stack[-1] = (node, index + 1)
                if not visited[neighbor]:
                    visited[neighbor] = 1
                    stack.append((neighbor, 0))
            else:
                finish_order.append(node)
                stack.pop()

    # 第二遍：按结束时间逆序在反向图上 DFS，一个连通块就是一个分量
    component = [0] * (n + 1)
    component_count = 0
    for start in reversed(finish_order):
        if component[start]:
            continue
        component_count += 1
        component[start] = component_count
        stack = [start]
        while stack:
            node = stack.pop()
            for neighbor in reverse_graph[node]:
                if component[neighbor] == 0:
                    component[neighbor] = component_count
                    stack.append(neighbor)

    return component, component_count


def contract(
    edges: EdgeList, component: list[int], component_count: int, n: int
) -> tuple[list[list[tuple[int, int]]], list[int], list[int], bool]:
    """缩点：返回 (分量 DAG, 入度, 分量大小, 是否无正环)。

    同一分量内出现权 1 边就是正环（要求 x > x），直接判无解。
    """
    size = [0] * (component_count + 1)
    for node in range(1, n + 1):
        size[component[node]] += 1

    dag: list[list[tuple[int, int]]] = [[] for _ in range(component_count + 1)]
    indegree = [0] * (component_count + 1)
    for u, v, w in edges:
        source, target = component[u], component[v]
        if source == target:
            if w:
                return dag, indegree, size, False  # 分量内权 1 边 = 正环
        else:
            dag[source].append((target, w))
            indegree[target] += 1

    return dag, indegree, size, True


def longest_path_in_dag(
    dag: list[list[tuple[int, int]]], indegree: list[int], component_count: int
) -> list[int]:
    """按拓扑序求每个分量的最长路值，初值全 1（每人至少一颗）。"""
    value = [1] * (component_count + 1)
    queue = deque(node for node in range(1, component_count + 1) if indegree[node] == 0)

    while queue:
        node = queue.popleft()
        for neighbor, weight in dag[node]:
            candidate = value[node] + weight
            if candidate > value[neighbor]:
                value[neighbor] = candidate
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return value


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

    graph, reverse_graph, edges, possible = build_graph(n, data)
    if not possible:
        print(-1)  # 自环形式的显式矛盾
        return

    component, component_count = kosaraju(graph, reverse_graph, n)
    dag, indegree, size, possible = contract(edges, component, component_count, n)
    if not possible:
        print(-1)  # 分量内有权 1 边，正环无解
        return

    value = longest_path_in_dag(dag, indegree, component_count)
    print(sum(value[c] * size[c] for c in range(1, component_count + 1)))


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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171/**
 * 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-21 08:50
 */
// 糖果：五类大小关系 + 每人至少一颗，求最小糖果总数。
// 全部写成下界形式 x_v >= x_u + w：
//   X=1 相等   -> 两个方向各一条 0 权边
//   X=2 少于   -> x_b >= x_a + 1（整数性让"少于"就是"至少少 1"）
//   X=3 不少于 -> x_a >= x_b，权 0
//   X=4 多于   -> x_a >= x_b + 1
//   X=5 不多于 -> x_b >= x_a，权 0
// 要求最少就是求最长路，初值 1（每人至少一颗）。
// 矛盾判定：权值只有 0/1，所以环权和 = 环上权 1 边的条数；而任何有向环都完全落在
// 某个强连通分量内，于是只需检查每个分量内部有没有权 1 边。全 0 环权和为 0，无害。
// 无解排除后缩点成 DAG，按拓扑序做最长路；同分量点强制相等，最后按分量大小加权求和。
//
// 强连通分量用 Tarjan 递归一遍 DFS 求出：在 DFS 树上用时间戳 dfn 与回溯值 low 判根，
// 用栈收集当前分量，出栈时就得到一个完整 SCC。只需正向图，不需要反图和第二遍遍历。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5; // 点数上界 N <= 1e5

struct Edge {
    int to;
    int w; // 0 表示"不少于"，1 表示"严格多于"
};

struct RawEdge {
    int u, v, w;
};

int n, k;
vector<Edge> g[MAXN];  // 正向图，Tarjan 只用这一张图
vector<RawEdge> edges; // 带权边表，缩点时要用

void add_edge(int u, int v, int w) {
    g[u].push_back({v, w});
    edges.push_back({u, v, w});
}

int dfn[MAXN];    // 第一次访问的时间戳，0 表示未访问
int low[MAXN];    // 从该点出发能回溯到的最小时间戳
int comp[MAXN];   // 每个点所属分量编号，从 1 开始
int tarjan_timer; // 时间戳计数器
int comp_cnt;     // 分量个数
int stk[MAXN];    // Tarjan 的分量收集栈
int stk_top;
bool in_stack[MAXN];

// 从 u 出发做一遍 DFS；返回时 u 所在的分量已经确定（可能已出栈）。
// low[u] == dfn[u] 说明 u 是本分量的根，此时弹出栈中 u 及其之后的所有点，
// 它们恰好构成一个强连通分量。
void tarjan(int u) {
    dfn[u] = low[u] = ++tarjan_timer;
    stk[stk_top++] = u;
    in_stack[u] = true;

    for (const Edge &e : g[u]) {
        int v = e.to;
        if (dfn[v] == 0) {
            tarjan(v);
            // 子树返回后，用子树能回溯到的最早时间戳更新自己
            if (low[v] < low[u]) low[u] = low[v];
        } else if (in_stack[v]) {
            // 回边或横叉边指向仍在栈中的点：只能拿 dfn[v] 更新 low[u]。
            // 指向已出栈点的边忽略——那些点属于已完成的分量，不可能再和 u 成环。
            if (dfn[v] < low[u]) low[u] = dfn[v];
        }
    }

    if (low[u] == dfn[u]) {
        comp_cnt++;
        while (true) {
            int v = stk[--stk_top];
            in_stack[v] = false;
            comp[v] = comp_cnt;
            if (v == u) break;
        }
    }
}

bool read_input() {
    cin >> n >> k;
    bool possible = true;

    for (int i = 0; i < k; i++) {
        int kind, a, b;
        cin >> kind >> a >> b;
        if (kind == 1) {
            add_edge(a, b, 0); // x_a >= x_b
            add_edge(b, a, 0); // x_b >= x_a
        } else if (kind == 2) {
            if (a == b) possible = false; // 自己少于自己
            add_edge(a, b, 1);            // x_b >= x_a + 1
        } else if (kind == 3) {
            add_edge(b, a, 0); // x_a >= x_b
        } else if (kind == 4) {
            if (a == b) possible = false; // 自己多于自己
            add_edge(b, a, 1);            // x_a >= x_b + 1
        } else {
            add_edge(a, b, 0); // x_a <= x_b 即 x_b >= x_a
        }
    }
    return possible;
}

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

    if (!read_input()) {
        cout << -1 << '\n'; // 自环形式的显式矛盾
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) tarjan(i);
    }

    // 缩点：分量大小、分量 DAG、入度
    vector<long long> comp_size(comp_cnt + 1, 0);
    for (int i = 1; i <= n; i++) comp_size[comp[i]]++;

    // 建立一个新的图
    vector<vector<Edge>> dag(comp_cnt + 1);
    vector<int> indegree(comp_cnt + 1, 0);
    for (const auto &e : edges) {
        int from = comp[e.u];
        int to = comp[e.v];
        if (from == to) {
            // 分量内出现权 1 边，要求 x > x，正环无解
            if (e.w) {
                cout << -1 << '\n';
                return 0;
            }
        } else {
            dag[from].push_back({to, e.w});
            indegree[to]++;
        }
    }

    // 缩点后是 DAG，按拓扑序求每个分量的最长路值，初值 1（每人至少一颗）
    vector<long long> value(comp_cnt + 1, 1);
    queue<int> que;
    for (int c = 1; c <= comp_cnt; c++) {
        if (indegree[c] == 0) que.push(c);
    }

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (const auto &e : dag[u]) {
            long long candidate = value[u] + e.w;
            if (candidate > value[e.to]) value[e.to] = candidate;
            if (--indegree[e.to] == 0) que.push(e.to);
        }
    }

    // 分量内每个点拿同样的糖，按分量大小加权求和
    long long answer = 0;
    for (int c = 1; c <= comp_cnt; c++) {
        answer += value[c] * comp_size[c];
    }
    cout << answer << '\n';

    return 0;
}

复杂度

SCC（两遍 DFS）与缩点 DAG 的拓扑 DP 都是 $O(N + K)$ ，空间 $O(N + K)$ 。

对比：如果把图直接交给 SPFA 判正环，最坏是 $O(NK) = 10^{10}$ ，必然超时。将图限定为 $\{0,1\}$ 权并利用“所有环都在 SCC 内”这条定理，才把这个判定降到线性。

总结

权值只有 0 和 1 时，“环权和”就等于“环上权 1 边的条数”，求正环退化成存在性判定。又因为所有有向环都在某个 SCC 内，全局判定变成“查每个分量内部有没有权 1 边”。无解排除后缩点成 DAG，按拓扑序求最长路，分量内同值，最后按分量大小加权求和。

目录

题意

思路