1. 题目到底在问什么一场学招式的“前置技能”大考打过 AtCoder 的人应该对 ABC226 的 C 题不陌生题面叫 “Martial artist”讲的是一个武术家去学各种招式每个招式有学习时长还可能依赖其他招式为前置条件。目标很简单学会第 N 个招式最少要花多久。听起来像是“把所有招式时间全加起来”就能过的题我第一次做的时候也这么想结果 WA 得满头问号。后来才反应过来不是每个招式都得学你只需要学“能通向第 N 个招式”的那些前置招式。换句话说这其实是一道披着模拟题外衣的图上遍历问题。标题里那个 “Contest 226” 指的就是 AtCoder Beginner Contest 226题号 C难度定位在 ABC 的偏中段适合刚接触图论、DFS、动态规划前菜的选手。它不像 A、B 那样秒杀但也不像 F、G 那样烧脑属于那种“想明白就豁然开朗想不明白就死磕一下午”的经典过渡题。这篇文章我会从题意拆解、建图思路、代码实现、以及坑点排查一条龙讲清楚。补全所有核心细节保证你看完不只 AC 这一道题还能顺手搞定同类的“依赖任务最短时间”问题。1.1 我喜欢先画一个“招式依赖树”再动手写代码题目输入结构大概是这样的第一行一个整数 N表示一共有 N 种招式。第 i 种招式会给出三个信息T_i 表示学会它需要的时间K_i 表示它依赖多少个前置招式然后紧跟 K_i 个整数表示依赖的招式编号。比如某个数据点长这样3 3 0 2 1 1 4 1 2这组数据的含义是第 1 招需要 3 分钟无前置直接能学第 2 招需要 2 分钟但必须先学第 1 招第 3 招需要 4 分钟但必须先学第 2 招目标永远是学会第 N 招。所以在上面的例子里想学会第 3 招就要学第 1、2、3 招加起来是 3 2 4 9 分钟。但题目狡猾的地方在于不是所有前面的招式都是第 N 招的前置依赖。有些招式可能是独立给出来“混淆视听”的你没学它照样能学会第 N 招。比如4 3 0 2 1 1 4 1 2 100 0第 4 招要学第 3 招而第 3 招依此类推根本不需要碰那招 100 分钟的“隐藏秘籍”。所以答案是 9而不是 109。明白这一点整道题的模型就清晰了把每个招式看成一个节点从节点 i 向它的所有前置招式连一条有向边表示“要想到达 i必须先经过这些节点”。那么问题就变成从节点 N 出发沿着反向依赖关系能走到哪些节点所有这些节点的时间加起来就是答案。提示题目保证了依赖关系中不会出现环也就是第 2 招依赖第 1 招、第 1 招又依赖第 2 招这种情况不会出现。这个保证很重要不然就得先做拓扑排序判断环了。1.2 核心关键词反向搜索、可达节点、权值和这道题之所以能在 ABC 里卡住不少人难点不在算法本身而在于你能不能跳出“把全部招式都学了”的思维定式。我习惯把它叫作“反向搜索求可达节点的权值和”。什么叫做反向搜索正常正向思路是从招式的源头往前推但要直接找到第 N 招的完整前置链最自然的办法其实是倒着来从第 N 招出发问“我依赖谁”再把依赖的那些招式的依赖也扒出来以此类推。这个过程用 DFS 或 BFS 都能做本质都是在一个有向图里做连通块遍历。另外我说一下这个“可达节点”的概念如果第 i 招直接或间接被第 N 招需要那么 i 就是可达节点。所有可达节点的时间加起来才是我们要的答案。不可达的招式哪怕它华丽得冒金光也跟我们无关。这道题还有一个非常经典的变体如果每个招式的前置关系不是一两层而是形成了一个很深的链条比如第 1000 招依赖第 999 招第 999 招依赖第 998 招……这样一直往前牵那么 DFS 的递归深度会非常大。这个时候如果用 Python 写得比较随意很容易踩中递归深度限制的坑。后面我会在代码实现部分专门讲怎么处理。2. 思路拆解为什么这是图论题而不是简单的累加题很多初学者看完题目之后的第一反应是“我开一个布尔数组标记哪些招要学然后从 1 到 N 循环把所有要学的招时间加起来不就行了”听起来挺合理但实现的时候你就会发现一个致命问题你怎么知道哪些招要学如果正着从 1 循环到 N遇到第 j 招时发现它依赖第 i 招就把第 i 招标记成需要学。可是这种“正向扫描 向后标记”的方法有一个漏洞假设第 j 招本身后来被发现根本不需要学因为它不在第 N 招的依赖链上那么之前你为了第 j 招而标记的第 i 招其实也是不需要学的。于是你就得反悔把第 i 招的标记撤掉。可撤掉之后你还要检查有没有其他招因为第 i 招被标记了这就会陷入反复撤销、反复检查的泥潭。所以正向遍历加标记在思路上看起来“模拟”实际上在逻辑上是要推翻重来的。而图上遍历则天然不存在这个问题从第 N 个节点出发能走到哪个节点哪个节点就是需要的走不到的你压根不用管。遍历过程自带“从目标反推需求”的语义不会出现“先多标再撤销”的尴尬。2.1 从生活化类比理解“反向依赖”你可以想象这样一个场景你是一个游戏策划要给玩家设计一套毕业装备每件装备都需要一些材料而这些材料本身又可能是由更基础的材料合成的。你的问题是要合成最终毕业武器总共需要哪些基础材料正常人不会把游戏里所有材料都刷一遍而是会打开“合成公式”从毕业武器开始逐级往下查武器需要什么需要的材料又需要什么一直查到最底层的原料为止。这个逐级下查的过程就是反向搜索。放到 Martial artist 里第 N 个招式就是最终毕业武器每个招式的 K_i 个依赖就是“合成公式”。我们不需要关心没有出现在这条依赖链上的任何材料也就是那些多出来的招式。2.2 用邻接表建图把依赖关系装进程序里既然要遍历图第一步自然是建图。这道题的数据规模我记得比较友好N 最大到 2×10^5 左右K 的总和在 2×10^5 量级所以用邻接表来存是完全没有压力的。这里有个小设计题目给的是“第 i 招依赖哪些招”。如果我们要从第 N 招反向搜可以直接用这个正向依赖列表在 DFS 时遍历第 i 招的依赖列表。也就是说建图时直接存每个节点的出边它依赖谁不需要额外建反图。反正追踪依赖链的时候你从 N 出发走到 i就是访问“i 依赖的节点们”方向正好和题目给出的列表一致。有一种新手容易犯的错是看到“反向搜索”四个字就以为需要把每条边反过来专门建一张反图。但在这道题里我们其实是在用“正向出边”模拟反向回溯因为题目给的每条边本身就是从“被依赖的招式”指向“依赖它的招式”吗不题目给的其实是“当前招式 - 它需要的前置招式”。也就是说边的语义天然就是“从目标往前提走”的方向。我们根本不需要建反图。我用大白话再梳理一遍第 i 项输入告诉你学完第 A 和 B可以学第 i 招从第 N 招开始推第 N 招需要第 A 和 B → 第 A 招需要第 C → 第 C 招需要第 D ……你顺着“招式 → 它的依赖”一直走到底自然就走完了整条链这就等同于在建好的图上做 DFS每个节点扩展出去的是“它依赖的前置招式”递归地访问下去即可。2.3 时间复杂度估算与解法合理性这种从第 N 个节点开始的 DFS每个节点至多被真正遍历一次用 visited 数组防止重复每条边也至多被扫描一次。所以总复杂度是 O(N K_total)也就是 O(N 边的总数)这是一个非常标准的线性复杂度。你可能要问为什么每个节点至多遍历一次因为一旦某个节点被访问过它的所有依赖信息就已经被累加过了后面不管哪个节点再依赖它都没必要重新遍历。用一个 visited 数组或者集合就能保证不重复计算。这个时间复杂度放在 2×10^5 的数据规模上跑理论上非常快Python 也不会超时。提示如果不加 visited 数组还是一个 DAG有向无环图理论上不会死循环但会导致同一个节点被重复访问非常多次。最坏情况下如果某个节点被很多上级招式依赖递归调用次数会指数级增长直接就 TLE 甚至爆栈了。所以 visited 数组不是可选项是必选项。3. 代码实现Python 与 C 双版本逐步讲解光讲理论不过瘾接下来直接上代码。我先把完整能 AC 的 Python 版本贴出来再逐行拆解关键部分并指出哪些地方容易踩坑。3.1 Python 版本基于 DFS 的完整题解import sys sys.setrecursionlimit(1 30) def main(): input sys.stdin.readline N int(input()) times [0] * (N 1) deps [[] for _ in range(N 1)] for i in range(1, N 1): tmp list(map(int, input().split())) times[i] tmp[0] k tmp[1] # 后面 k 个是前置技能编号 deps[i] tmp[2:2 k] visited [False] * (N 1) ans 0 def dfs(u): nonlocal ans if visited[u]: return visited[u] True ans times[u] for v in deps[u]: dfs(v) dfs(N) print(ans) if __name__ __main__: main()这段代码的核心就一个 dfs(u)如果 u 被访问过直接返回防止重复累加时间标记 visited[u] True防止后续再次进入累加当前招式的时间 times[u]遍历 deps[u] 里所有前置招式递归访问调用 dfs(N) 之后所有第 N 招依赖链上能抵达的节点都被访问过答案自然就是所有可达节点的时间总和。这里有一个很多人会忽略的细节Python 的递归深度默认只有 1000。而这道题如果依赖链路比较深比如 N 条招式的依赖形成一长串递归深度可能超过 1000。所以第一行就写上sys.setrecursionlimit(1 30)把递归上限提得足够高。我见过不少人在本地跑小样例没问题一提交就 RecursionError就是这个原因。3.2 不用递归的写法BFS 队列版如果你不喜欢递归或者担心极端情况下递归仍然有风险可以改用 BFS用队列存储待访问节点完全避开递归深度问题。from collections import deque def main(): import sys input sys.stdin.readline N int(input()) times [0] * (N 1) deps [[] for _ in range(N 1)] for i in range(1, N 1): tmp list(map(int, input().split())) times[i] tmp[0] k tmp[1] deps[i] tmp[2:2 k] visited [False] * (N 1) ans 0 q deque([N]) while q: u q.popleft() if visited[u]: continue visited[u] True ans times[u] for v in deps[u]: if not visited[v]: q.append(v) print(ans) if __name__ __main__: main()BFS 和 DFS 在这道题上效果完全一致因为你要的不是“访问顺序”而是“所有可达节点的权值和”。BFS 的好处是不会踩递归深度的坑Python 环境下更稳。如果追求写起来简单DFS 更简洁如果追求极致稳定BFS 是我的首选。3.3 C 版本竞赛中最常见的写法C 在 AtCoder 上依旧是最主流的选择这里也给出一个模板级别的实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorlong long t(N 1); vectorvectorint dep(N 1); for (int i 1; i N; i) { int k; cin t[i] k; dep[i].resize(k); for (int j 0; j k; j) { cin dep[i][j]; } } vectorbool visited(N 1, false); long long ans 0; functionvoid(int) dfs [](int u) { if (visited[u]) return; visited[u] true; ans t[u]; for (int v : dep[u]) { dfs(v); } }; dfs(N); cout ans \n; return 0; }注意这里我把t[i]定义成了long long。因为 N 最大 2×10^5 时每个招式的时间上限是 10^9累加起来可能达到 2×10^14 这个量级明显超过 int 的范围。这是很多 C 新手容易犯的错WA 一次才发现要开 long long。提示这道题的时间总和虽然没有开启高精度需要的恐怖数据量但用 long long 是竞赛选手的基本素养。只要你看到“累加”二字就习惯性地往 long long 上想能省下不少调试时间。4. 常见问题与排查技巧实录我自己从第一次 WA 到后来能三分钟 AC中间踩过不少坑。把常见的问题整理成一份速查表希望能帮你少走弯路。常见问题出现原因解决方案答案比预期大很多多算了不在依赖链上的招式确认是否从 N 出发做 DFS/BFS而不是从 1 到 N 全部累加答案比预期小访问了节点但未累加时间或者累加位置不对在visited[u] True之后立刻加 time[u]不要等出队列再加递归爆栈 RecursionErrorPython 默认递归深度只有 1000在代码开头加sys.setrecursionlimit(1 30)或者改用 BFS使用 C 计算结果错误int 溢出将时间数组与最终答案都定义为 long long重复计算某个招式时间没有去重导致同一个招式的耗时被加入多次必须使用 visited 数组访问过就跳过输入解析出错N 行输入中 K 值后面有的行为 0有的行为多值处理不当会越界用tmp[2:2 k]精确截取不要用tmp[2:]硬切后假设一定有 k 个4.1 最容易翻车的细节visited 标记的时机我见过不少人在 BFS 版本里把 visited 的赋值放在从队列取出节点之后就像我上面写的那样。这种写法没问题因为你取出一个节点进入循环体后立刻判断是否访问过然后才累加。但问题出在另一种写法里——如果你在入队时没设置 visited取出时才设置就可能出现同一个节点被多个“上层节点”重复加入队列的情况。举个例子假设第 5 招和第 6 招都依赖第 3 招。BFS 从 N 出发把第 5 和第 6 入队它们俩出队时都发现第 3 招还没被访问过于是第 3 招被加入了两次队列。这样一来第一次取出第 3 招时累加时间并标记。第二次再取出第 3 招时发现 visited 已经是 True跳过。最终答案不会错但队列里会多出一些冗余节点造成不必要的性能损耗极端情况下可能接近 O(N^2)。更干净的写法是在把一个节点加入队列的那一刻就标记 visited。但如果你像我一样喜欢在取出时判断那必须保证入队前不重复入队也就是在遍历出边时加一个if not visited[v]的条件。两种方式选一种并坚持到底不要混着来。4.2 手动模拟样例3 分钟吃透算法流程为了加深理解我们跑一个稍微复杂的例子4 5 0 3 1 1 2 1 2 10 2 1 3招式 1耗时 5无依赖招式 2耗时 3依赖招式 1招式 3耗时 2依赖招式 2招式 4耗时 10依赖招式 1 和 3目标是学第 4 招。调用 dfs(4)标记 4ans 10遍历依赖 [1, 3]先递归 dfs(1)标记 1ans 151 无依赖返回再递归 dfs(3)标记 3ans 17依赖列表是 [2]继续 dfs(2)dfs(2)标记 2ans 20依赖列表是 [1]但 1 已经被访问直接返回最终 ans 20恰好等于 10 1 2 3 的总和也就是招式 4、1、3、2 的时间加起来。这个例子清楚地展示了 visited 的作用招式 1 没有被重复累加。4.3 代码里不建议用的几种写法写这题的实践里有些写法虽然能通过但容易把自己绕晕我不太推荐。第一种是递归时把累加逻辑放在visited判断之外。比如def dfs(u): if visited[u]: return ans times[u] # ans 是 nonlocal for v in deps[u]: visited[v] True dfs(v)这里把visited[v] True放在调用前看似没问题但如果后续某处忘了设置或者时序不一致很容易出现遗漏累加的问题。更好的规范是统一在进入 dfs 时设置 visited不依赖外部预先标记。第二种是在递归函数里直接修改全局 ans却忘记声明 nonlocal。Python 的闭包规则很严格如果你在嵌套函数里对ans做加法必须写上nonlocal ans否则会报错或把ans当成局部变量。很多新手就在这个细节上卡住一脸懵地看着 UnboundLocalError。第三种是试图用二维布尔数组来标记“哪些招需要学”然后一层层推到前面。这个方法在逻辑上绕代码长而且容易错。既然有图论模型这么干净的解法不要自讨苦吃。5. 从一道题到一类题依赖关系问题的通用套路Martial artist 这道题让我特别想聊的是它代表了一类非常常见的问题给定一个依赖关系图求完成某个目标需要的最小代价。这类问题在游戏技能树、软件构建、课程选修、编译依赖里全都能见到。5.1 换个条件还能怎么考如果题目把“学会第 N 招所需时间”改成“所有招式都学会所需时间”那问题就简单到变成把时间数组直接求和。但这道题的核心竞争力在于它只要求学第 N 招所以有些节点是不用管的。这正是“部分依赖”带来的搜索需求。如果题目改成“每个招式的学习时间还取决于当前已经学会了哪些招”那就不是单纯图遍历了可能要上 DP。如果依赖关系允许环那就得先判环或者缩点再用拓扑排序。如果招式数量变小、但每个招式依赖的招很多那可能要考虑状态压缩 DP。但不管怎么变第一板斧永远是建图 遍历。这一步不会变也不可能变。所以我一直跟人讲图论的基础打牢了后面很多题就是套模板加上理解题意的事。5.2 同类型题目拓展从 ABC226 C 到更多题目想要在 AtCoder 上刷类似题我还可以推荐几个典型的依赖关系相关题目ABC 277 E 之前的一些图遍历题有助于加深 DFS 遍历能力ABC 007 C 是经典的 BFS 最短路模板题练好 BFS 基础ABC 168 D 是“从 1 出发标注父节点”的题目和这道题的 visited 思路有相通之处把这些题都刷一遍你就会发现“图上的可达性问题”是非常有共性的无非是从起点出发一路标记访问直到无法扩展为止。6. 关于这道题我想再多聊几句Martial artist 这个题面我个人挺喜欢的因为它的背景故事非常容易懂不用去啃那些艰深的数学定义。但正因为背景简单很多人反而掉以轻心觉得不就是加法吗结果一交上去就 WA。这道题教会我的最重要的一件事是拿到题目先别着急写代码先花两分钟想清楚模型是什么再动手。代码只有十几行但如果模型没想对代码越长你越难查错。这也是我在无数场模拟赛里总结出的经验思路不清晰时写的每一行代码都是隐患。反过来只要模型想清楚了哪怕代码写得丑一点AC 也就是时间问题。最后再分享一个小技巧如果你的时间足够建议你在本地分别用 DFS 和 BFS 两种写法各写一遍然后跑同一个随机数据生成器对比它们的输出。这不只是练手更是逼自己把两种遍历的实现细节都吃透。下次再遇到类似题目你就不需要纠结用哪种方法了因为在你眼里它们已经统一成同一种思路了。