学习目标
前置知识与环境
先阅读 第 14 章对应小节，并确保本机可使用 C++17。首次运行可执行 make doctor；Windows 未安装 Make 时可在仓库根使用 pnpm 命令。
题目
有 n 个地窖，每个地窖有一定数量的地雷；给出若干条编号从小到大的单向通道。选择任意起点并沿通道前进，使经过地窖的地雷总数最大。输出路径和最大总数；若总数并列，输出编号序列字典序最小的路径。
输入格式
第一行 n，第二行 n 个地雷数，第三行通道数 m，随后 m 行为 u v（u<v）。
输出格式
第一行输出路径编号，第二行输出最大地雷总数。
数据范围
1 ≤ n ≤ 20，地雷数非负且不超过 300，通道不重复。
样例输入
text
4
5 10 5 20
4
1 2
1 3
2 4
3 4样例输出
text
1 2 4
35做题前先填状态卡
| 问题 | 本题答案 |
|---|---|
| 状态 | best[i] 表示从 i 出发可取得的最大地雷数，并同时保存对应路径。 |
| 选择 | 停止在 i，或选择一条 i→j 通道继续。 |
| 转移 | best[i]=mine[i]+max(best[j])，相等时比较完整路径字典序。 |
| 初值 | 出度为 0 时路径只有 i。 |
| 顺序 | 按编号从大到小，或记忆化 DFS。 |
| 答案 | 所有起点中权值最大、再按路径字典序最小者。 |
不要急着写循环。先用一个最小输入手算状态表，再检查每个右侧依赖是否已经计算；如果依赖来自“当前物品的新状态”，还要说明这是否意味着允许重复选择。
复杂度目标
时间 O(n+m) 加路径比较开销，空间 O(n+m)。
测试设计提示
公开测试共 20 组、总分 100 分，覆盖样例、最小规模、单行/单列或单元素、不可达/全负/重复值等题型边界，以及容易暴露循环方向和初始化错误的回归输入。测试只接受标准输出；调试信息请写到标准错误。
运行与评分
powershell
cd labs/chapter-14/exercise/E-14-07-mine-digging
make run
# 没有 Make 时，在仓库根执行
pnpm lab:run -- labs/chapter-14/exercise/E-14-07-mine-digging
# 作者与 CI 的严格检查
pnpm lab:verify -- labs/chapter-14/exercise/E-14-07-mine-digging完成清单
思考与复盘
- 如果改用另一种状态定义，转移和循环顺序会怎样变化？
- 哪个最小反例最容易暴露「只记录前驱而不定义并列规则，会让标准输出依赖遍历顺序。」？
- 能否压缩空间？压缩后会不会覆盖本轮仍需读取的状态？
题目来源与课程化说明
核心问题参考 洛谷 P2196。本 Lab 为课程标准输入/输出环境重新表述题面，并独立编写参考实现与测试数据；不复制第三方题解、代码或隐藏测试。