Contest 226 - C - Martial artist这道题出自 AtCoder Beginner Contest 226是那次比赛里第三题。题面讲一位叫 Takahashi 的武术家要学招式每个招式有学习时长还可能有前置招式想学某个招式前必须先把它的前置招式全部学会。目标很简单学会第 N 个招式最少要花多少分钟。但真正动手之后你会发现这题披着模拟题的外衣内核却是一道图论题——而且从哪个方向搜决定了你的代码是干净利落还是又臭又长。这篇博文把从读题到 AC 的完整过程记录下来适合准备 ABC 入门、或者刚接触 DFS/BFS 基础图的选手参考我会把每一步选择背后的原因也一并讲清楚。1. 先读懂题武术家到底在练什么1.1 题面还原与核心规则原题的描述很简单Takahashi 是一名武术家他想学会编号从 1 到 N 的招式。第 i 个招式的学习耗时是 T_i 分钟并且学习它之前必须先学会 K_i 个指定的招式。注意K_i 可以为 0也就是这个招式没有任何前置门槛随时能学。整个训练过程没有复杂的并发或顺序约束一个人同一时间只能专注练一个招式。所以结论很直接如果最终要学的技能集合是 S那么总耗时就是 S 里所有招式耗时之和。很多人刚开始会被“最少需要多少分钟”这几个字带偏以为要算最优调度或者并行安排实际上题目根本没给你并行训练这个设定老老实实把依赖链上的所有时间加起来就行。题目的目标是学会第 N 个招式。注意不是学会全部招式也不是学会某个给定集合而是仅仅最后一个招式。这是整道题最重要的一个限定条件后面所有思路都围绕它展开。1.2 数据规模与输入格式输入格式如下第一行是 N接下来 N 行每行描述一个招式。第 i 行开头是 T_i 和 K_i如果 K_i 大于 0后面还跟着 K_i 个整数表示这个招式需要的前置招式编号。所有编号都是 1-based也就是从 1 到 N。数据规模方面N 最大能到 2×10^5每个招式的耗时 T_i 可以到 10^9 级别。这个规模意味着不能用 O(N^2) 的暴力必须在 O(N 总前置数) 的复杂度内解决。另外题目保证每个招式的前置招式编号一定小于它自身的编号也就是 A_{i,j} i。这个性质很关键它保证了整个依赖图是一个有向无环图不存在循环依赖。换句话说按照编号从小到大天然就是一个合法的拓扑顺序。1.3 这题真正考的是什么很多人第一眼会认为这题是模拟从第 N 个招式开始递归地找前置把所有需要学的招式标记出来然后求和。这确实是正确方向。但难点在于如果你没有建立图论的视角很容易陷入“正向遍历所有技能判断哪些被需要”的坑里。这题真正想考察的是从目标节点出发在一个有向图中做“反向可达性搜索”。你需要的不是整个图的信息而是目标节点 N 的依赖闭包。在图里依赖关系是边前置技能是前驱节点从 N 出发沿着“前置关系”反向走能走到的所有节点就是必须学的招式再把这些招式的时间加总就是答案。2. 思路选型为什么反向 DFS 才是这题的钥匙2.1 正向拓扑排序的“过度设计”我先说说我一开始的错误思路这个坑很有代表性。看到“技能依赖前置技能”第一反应就是拓扑排序把所有招式按依赖关系排好序然后顺着拓扑序从前往后累加时间最后输出第 N 个招式的时间。听起来很合理但仔细一算就发现问题了。拓扑排序会处理所有 N 个技能但题目只要第 N 个技能的依赖信息。如果 N 的依赖链很短或者很多技能与第 N 个招式完全没有关系那这些无关技能的计算完全是白费。更麻烦的是单纯顺着拓扑序累加还有重复计算问题两个不同招式可能依赖同一个公共前置招式如果简单地把每个技能的前置时间累加这个公共前置会被重复计数答案就会偏大。这不是说拓扑排序不能做它需要额外处理去重逻辑代码会明显变长。对一个 ABC 的 C 题来说明显有更轻量、更贴合的解法。2.2 反向思考的关键一步正确做法是反过来从第 N 个招式出发沿着“前置招式”这条边往回走。每走到一个招式就把它标记为“需要学”然后把它的耗时加入答案。由于题目保证前置招式的编号一定小于当前招式所以反向走的时候编号始终在递减不存在环也不会走入“不需要学”的分支。这个思路的本质是只探索“必要节点”。从 N 出发能到达的每一个点都是学会 N 所绕不开的技能从 N 出发到不了的技能不管它多复杂、依赖多深都和第 N 个招式无关直接忽略。也就是说你不需要关心全图的整体结构只关心目标节点 N 能反向触达的那一小块。我习惯用一个生活类比你要做一道复杂的菜只需要找出这道菜需要的所有食材和半成品然后去采购。你不会把整个超市的所有货架都逛一遍也不会把所有东西都买回家。反向 DFS 就是“按需寻源”而拓扑排序是“把超市全部盘点一遍再决定买什么”。2.3 复杂度分析与选型结论反向 DFS / BFS 的复杂度非常干净每个节点最多被访问一次每条依赖边最多被检查一次。假设总前置数为 M则时间复杂度是 O(N M) 中的实际访问量最多也就 O(N M)空间复杂度 O(N M) 用来存依赖边和访问标记。在 N 最大 2×10^5 的约束下这个复杂度完全够用Python 也能轻松跑进时间限制。而如果选择拓扑排序虽然复杂度同样是 O(N M)但常数更大逻辑更绕还容易在去重上翻车。所以结论很明确这题的正解就是反向搜索DFS 或者 BFS 都行核心思想一致区别只在实现细节。顺便说一句为什么很多题解推荐 DFS 而不是 BFS因为这里没有求最短路径的需求DFS 实现起来更短用一个递归函数加一个访问标记就完成了。但考虑到递归深度的问题用迭代栈写 DFS 或者直接用队列写 BFS 也完全没有问题。我下面给出的代码里迭代栈版本是我个人最推荐的——既保持了 DFS 的简洁语义又避免了递归爆栈的隐患。3. 完整代码实现与逐行拆解3.1 Python 递归版先看递归版这是最直观的写法。先读入数据把每个招式的耗时存到 cost 数组把前置依赖存到 need 列表下标统一从 0 开始。然后从第 N-1 个招式也就是输入中的第 N 个开始 DFS。import sys sys.setrecursionlimit(1 20) input sys.stdin.readline n int(input()) cost [0] * n need [[] for _ in range(n)] for i in range(n): row list(map(int, input().split())) cost[i] row[0] k row[1] for j in range(k): need[i].append(row[2 j] - 1) vis [False] * n def dfs(u): if vis[u]: return 0 vis[u] True total cost[u] for v in need[u]: total dfs(v) return total print(dfs(n - 1))这里最关键的是 dfs 函数里的if vis[u]: return 0。它保证了同一个技能即使被多个前置技能依赖也只会被累加一次。如果你把这一行去掉公共前置会被反复计入答案结果一定偏大。这个函数的设计思路是“如果这个技能已经被访问过说明它的耗时已经算进答案了本次调用不应该产生任何新增贡献直接返回 0”。3.2 Python 迭代栈版推荐递归版的隐患在于 Python 默认递归深度只有大约 1000 层虽然题目依赖链最长不会超过 N但 N 有 2×10^5一旦出题人构造一条长链递归版就会在运行时报 RecursionError。设置sys.setrecursionlimit(1 20)能缓解但有些在线评测环境对递归栈本身有限制用迭代栈一劳永逸。import sys input sys.stdin.readline def main(): n int(input()) cost [0] * n need [[] for _ in range(n)] for i in range(n): row list(map(int, input().split())) cost[i] row[0] k row[1] if k: need[i] [x - 1 for x in row[2:2 k]] vis [False] * n stack [n - 1] vis[n - 1] True ans 0 while stack: u stack.pop() ans cost[u] for v in need[u]: if not vis[v]: vis[v] True stack.append(v) print(ans) if __name__ __main__: main()注意这里我把vis[n - 1] True放在入栈之前避免重复入栈。每次从栈里弹出一个节点先加它的耗时再把它所有未被访问的前置技能压入栈中。由于题目保证依赖编号一定小于自身栈内元素不会出现环整体逻辑非常稳定。3.3 C 参考实现如果你习惯用 C 参赛参考实现如下。核心逻辑和 Python 迭代版一致唯一的区别是使用了long long来存答案防止累加时溢出。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long cost(n); vectorvectorint need(n); for (int i 0; i n; i) { int k; cin cost[i] k; need[i].resize(k); for (int j 0; j k; j) { cin need[i][j]; need[i][j]--; } } vectorbool vis(n, false); stackint st; st.push(n - 1); vis[n - 1] true; long long ans 0; while (!st.empty()) { int u st.top(); st.pop(); ans cost[u]; for (int v : need[u]) { if (!vis[v]) { vis[v] true; st.push(v); } } } cout ans \n; return 0; }在实际比赛中C 的vectorvectorint用来存前置边就够了。如果你担心内存碎片也可以用邻接表的数组形式但选手赛里vector的写法在 2×10^5 规模下完全扛得住不需要额外优化。4. 手动跑一遍流程从样例到边界数据4.1 用官方样例完整走一遍官方给的样例输入是3 3 0 4 1 1 2 2 1 2意思是技能 1 耗时 3无前置技能 2 耗时 4需要先学技能 1技能 3 耗时 2需要先学技能 1 和 2。目标是学会技能 3。用迭代栈模拟一遍初始化stack [2]表示 0-based 下的技能 3vis[2] trueans 0。弹出 2ans cost[2]等于 2。遍历 need[2] 得到前置 [0, 1]。技能 0 未访问标记后入栈。技能 1 未访问标记后入栈。弹出 1ans cost[1]等于 6。遍历 need[1] 得到前置 [0]但技能 0 已经被访问过跳过。弹出 0ans cost[0]等于 9。技能 0 无前置直接结束。输出 9。注意一个细节技能 1 同时是技能 2 和技能 3 的前置但它在被弹出只是累加了一次。如果去掉 vis 数组技能 1 会被两个分支各访问一次答案就会变成 2 4 3 3 12明显错误。4.2 一个专门用于观察重复依赖的样例再构造一个更极端的例子来展示 vis 标记的作用4 10 0 5 1 1 5 1 1 1 2 2 3输入解读技能 1 耗时 10无前置技能 2 耗时 5需要学技能 1技能 3 耗时 5需要学技能 1技能 4 耗时 1需要学技能 2 和 3。目标技能 4 的依赖链里技能 1 被技能 2 和 3 同时依赖。正确结果应该是 1 5 5 10 21因为技能 1 只需要学一次。用迭代栈模拟stack [3]ans 0。弹出 3ans 1前置是 [1, 2]入栈。弹出 2ans 5前置是 [0]入栈。弹出 1ans 5前置是 [0]但技能 0 已被访问跳过。弹出 0ans 10结束。答案 21正确。这个例子如果交给递归版但没有 vis 保护结果就是 1 5 10 5 10 31差了正好一个 10——这就是公共前置被重复计数的标准症状。以后你在比赛里发现答案莫名偏大基本就是少了这个去重标记。4.3 如何快速验证你的代码写完后不要急着提交先自己构造几组边界数据。第一组N1只有一行10 0输出应为 10因为没有前置学会第 1 个招式就是它的耗时本身。第二组长链依赖例如 N4技能 2 依赖 1技能 3 依赖 2技能 4 依赖 3每个耗时都是 1答案是 4。第三组全部没有前置答案是 T_N 本身。这几组数据覆盖了“单节点”“长依赖链”“无依赖”三种情况能帮你把大多数低级错误提前拦下来。5. 常见问题与排错速查5.1 答案偏大找了半天没发现问题这是最典型的 Bug忘了去重。症状是输出总是比预期答案大而且大出的部分刚好是某个公共前置的耗时。原因就是递归/搜索时没有加 visited 判断同一技能被不同分支重复累加。如果你用的是递归写法检查 dfs 函数开头是否写了if vis[u]: return 0如果用 BFS 或迭代栈检查入栈前是否判断了not vis[v]。5.2 递归爆栈 RecursionErrorPython 默认递归深度大约 1000在长依赖链下必炸。解决办法有两个一是在递归版开头加sys.setrecursionlimit(1 20)但这只是调高上限极端情况下依然可能受操作系统栈限制二是直接换迭代栈版完全避免递归调用。我个人倾向后者尤其在大规模数据下更省心。5.3 下标没从 1 转 0答案错得离谱AtCoder 输入是 1-based而 Python 数组下标是 0-based。读入前置技能编号时一定要减 1。如果你忘了减 1need里存的编号整体偏大 1访问时可能越界更隐蔽的是Python 列表的负索引会让arr[-1]悄悄访问最后一个元素代码不报错但结果完全错误。建议读入后立刻处理并且用一个简单的样例验证第一行的技能 1 是否对应数组下标 0。5.4 C 用 int 存答案导致溢出T_i 最大可以到 10^9N 最大 2×10^5理论答案上限会达到 2×10^14这远远超过了 32 位 int 的范围。如果你用 C答案和 cost 数组务必声明为long long。Python 的 int 没有这个顾虑但也别写成//之类不小心截断的逻辑。5.5 常见问题速查表症状可能原因解决办法答案偏大公共前置被重复累加添加 vis 标记访问过的节点不再统计运行时递归错误递归深度超限调高 setrecursionlimit 或改用迭代栈答案完全错误下标未从 1 转 0读入前置技能时减 1C 输出负数int 溢出换成 long long输入超时使用了低效的读入方式用 sys.stdin.readline 或 ios::sync_with_stdio(false)5.6 一个容易被忽略的小细节题目保证前置招式编号小于自身所以从 N 反向搜索时不可能出现环。但如果哪天你遇到类似的题出题人没有给这个保证你就需要额外考虑环的情况。一般的做法是要么先用拓扑排序判环要么在 DFS 时记录“当前递归栈内”的节点发现重复就说明有环。本题不需要但养成这个意识遇到变种题时不至于慌。6. 题目之外的通用套路依赖类问题怎么想6.1 “目标单一依赖复杂”先想按需搜索这题的价值不只在 AC 本身更在于一种解题取向。很多题目的描述都有一个“全局结构”N 个技能、若干依赖关系、一堆约束条件。如果题目问的是“全局最优”或者“所有节点都需要”,那往往要全量遍历或做全局分析但如果问的是“只关心某一个特定节点/目标”那么“按需搜索”往往是最高效、最简单的方式。这类题目的信号词很典型给定一个有向无环图每个节点有代价节点之间有前置依赖询问到达某个目标节点最少需要多少总代价。一旦识别出这个模式直接反向 DFS/BFS从目标节点出发收集依赖闭包就八九不离十了。6.2 vis 标记与记忆化搜索的关系有读者可能会问这题能不能用记忆化搜索本质上是能的。如果你定义一个solve(u)表示“学会技能 u 所需的新增时间”那么solve(u) cost[u] sum(solve(v) for v in need[u])但要加一个条件如果 u 已经被处理过solve(u)返回 0。这其实就是记忆化的变体只不过这里的“记忆”不是缓存子问题的结果而是缓存“该节点是否已经被收入答案”。其实更好理解的方式是你不需要保存每个子问题的完整返回结果只需要一个布尔数组记录访问状态。访问过就跳过这比传统记忆化搜索还要轻量。实际编码时我建议直接做 vis 标记不要把它包装成记忆化递归后者容易让你在“返回什么值”上绕晕。6.3 后续练习方向如果你刚做透这一题想趁热打铁巩固可以从这几个方向延伸。第一做几道“反向建图”的题比如需要从多个终点反向搜索的题目你会慢慢体会到反向思维在图上有多常用。第二练习 BFS 和 DFS 两种写法互换同一个题用队列写一遍、用栈写一遍、用递归写一遍弄清楚每种写法的注意点。第三尝试给这题加一些变式比如求“学会第 N 个招式的最少天数”如果允许每天并行学多个招式解法又会变成按层级统计……从一道题延伸出多种问法是提升图论感觉很有效的方式。我个人的体会是这题我第一次做的时候用的是拓扑排序全量处理代码写了六十多行还纠结去重逻辑后来第二次遇到类似题直接反向栈遍历二十行不到就写完了。自那以后但凡看到“求某个目标节点的依赖信息”我都会下意识地先从终点倒着搜一遍——这个习惯让我在不少比赛里省下了大量时间。希望这篇记录也能帮你把这道经典 C 题一次吃透。