挖地雷

形式化题目

给定 $n$ 个地窖，第 $i$ 个地窖有 $a_i$ 枚地雷。再给出一个有向边集合 $\{x \to y\}$ ，保证 $x < y$ ，并以 0 0 结束。边表示可以从 $x$ 走到 $y$ ，且从一地窖出发后只能选择一条出边继续走；当某点没有出边时停止。

要求从任意一个地窖出发，找一条有向路径，使得路径上所有地窖的地雷数之和最大。输出这条路径（点编号用 - 连接）以及最大地雷总数。

正解

思路

因为所有边都从小编号指向大编号，所以整张图是一个有向无环图（DAG）。点编号 $1 \sim n$ 本身就是一个拓扑序：想计算“从 $u$ 出发能走多远”时， $u$ 能到达的所有点都已经计算过了。

设：

$dp[u]$ ：从地窖 $u$ 出发，一直走到无路可走，最多能挖到的地雷总数。
$nxt[u]$ ：最优路径中 $u$ 下一步要去的地窖编号。若 $u$ 后面不再走，则 $nxt[u]=0$ 。

由于 $u$ 的所有后继 $v$ 都比 $u$ 大，可以从 $n$ 倒推到 $1$ 计算：

dp[u] = a_u + \max_{u \to v} dp[v]

如果 $u$ 没有出边，则 $\max$ 项为 $0$ ， $dp[u]=a_u$ 。

全局最优起点就是 $dp[1..n]$ 中的最大值；从该起点沿 $nxt$ 数组依次走，即可得到完整路径。

样例 DP 表

以下表展示样例按 $u=6,5,\dots,1$ 逆序计算的结果。

$u$	$a_u$	出边指向	已算出的 $dp$ 候选	$dp[u]$	$nxt[u]$
6	5	无	—	5	0
5	4	6	5	9	6
4	5	5, 6	9, 5	14	5
3	20	4	14	34	4
2	10	4	14	24	4
1	5	2, 4	24, 14	29	2

最大 $dp$ 出现在 $u=3$ ，沿 $nxt$ 得到 $3 \to 4 \to 5 \to 6$ ，总和 $34$ 。

代码

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#!/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-11 22:00
# update_at: 2026-07-11 22:00

import sys

NEG = -10**18


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [0] + [next(data) for _ in range(n)]          # 1-indexed 地雷数
    g = [[] for _ in range(n + 1)]
    while True:
        x, y = next(data), next(data)
        if x == 0 and y == 0:
            break
        g[x].append(y)

    dp = [0] * (n + 1)                                # 从 i 出发能挖到的最多地雷
    nxt = [0] * (n + 1)                               # 最优路径的下一个点，0 表示结束
    for u in range(n, 0, -1):
        best, nxt_u = NEG, 0
        for v in g[u]:
            if dp[v] > best:
                best, nxt_u = dp[v], v
        dp[u] = a[u] + (best if best != NEG else 0)
        nxt[u] = nxt_u

    start = max(range(1, n + 1), key=lambda i: dp[i])  # 全局最优起点
    path: list[str] = []
    u = start
    while u:
        path.append(str(u))
        u = nxt[u]

    print('-'.join(path))
    print(dp[start])


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(n + m)$ ， $m$ 为边数。每个点处理一次，每条出边枚举一次。
空间复杂度： $O(n + m)$ ，存储邻接表、 $dp$ 、 $nxt$ 数组。

总结

本题的本质是在一个边方向严格递增的 DAG 上求点权和最大的路径。利用拓扑序的显式结构，直接用逆序线性 DP 即可： $dp[u]$ 只依赖于比 $u$ 大的点，无后效性；路径通过 $nxt$ 数组还原。实现时注意输入以 0 0 结束。

目录

形式化题目

正解

思路

样例 DP 表

代码

复杂度

总结