1. 从题目说起P1113 到底在解决什么问题P1113 [USACO02FEB] 杂务这是一道经典的 USACO 早期题目题面看着特别像流水账一堆家务活又是给牛挤奶、又是清理马厩、又是给谷仓刷漆每件事还要先干完别的活才能开始最后问你所有活都干完最早要多久。我第一次刷到这题的时候第一反应是“这不是模拟题吗”直接扫一眼输入以为按顺序累加就完事了。交上去 WA 得明明白白回头仔细一读才发现问题根本没有那么简单——每个杂务之间是有前置依赖的而且前置任务可能不止一个任务之间还能并行做。说白了这就是一道藏在“家务活”包装下面的图论动态规划题。先说结论这道题本质上要你求的是一个有向无环图上的最长路径和用大白话讲就是——在一个任务依赖关系形成的网络里找出从起点到终点所有路线中耗时最长的那个总和这个最长总和就是完成所有任务的最早时间。为什么是“最长路”而不是“最短路”因为某些任务可以同时开工所以真正卡住整体进度的一定是那条“一环扣一环、中间不能并行压缩”的路径。你所有任务的最早完成时间就等于最长的那条依赖链的总耗时。这跟项目管理里的“关键路径法CPM”是同一个思路搞懂这道题等于顺手搞懂了工程排期的核心模型。这道题很适合什么阶段的人刷我觉得如果你是刚开始学拓扑排序、刚接触树形DP或者DAG上DP的新手这题是一个极好的练手素材。它不涉及复杂的数据结构代码量也不大但能帮你把“图模型抽象——依赖关系分析——动态规划转移”这条完整的解题链路走一遍。就算你现在还不会拓扑排序看完这篇也能搞明白它到底是干嘛的。2. 题意拆解两个容易踩的坑先把题面的细节和你捋一遍因为后面所有算法都建立在对题意准确理解的基础上。2.1 输入格式到底长什么样输入大概是这样的7 1 5 0 2 2 1 1 0 3 3 2 1 2 0 4 6 1 1 0 5 1 2 4 0 6 8 2 2 4 0 7 4 3 3 5 6 0第一行是杂务总数 N。接下来 N 行每行描述一个杂务第一个数字是杂务编号从 1 开始第二个数字是完成这个杂务本身需要的时间第三个数字是前置杂务的数量 m接下来 m 个数字是这些前置杂务的编号最后用一个 0 表示该行结束。以样例第 2 行为例2 2 1 1 0意思是“杂务2需要2小时完成它依赖1个前置任务也就是杂务1”。第 5 行5 1 2 4 0则表示“杂务5需要1小时依赖杂务4没有别的依赖了”。注意m 0 表示这个任务没有任何前置条件可以一开始就做。第 1 行末尾那个 0 就是这种情况。2.2 最容易误解的“并行执行”这道题最大的坑在于题目默认你有三头六臂所有没有依赖关系的任务同一时间都能做而且一个人能同时做所有能做的活不存在资源竞争。举个例子如果任务1需要5小时任务2需要2小时而任务2不依赖任务1那这两个任务可以同时开工总共只需要5小时而不是7小时。很多第一次做这道题的人都会栽在这里以为是在模拟单线程执行的队列结果把并行时间当成串行时间算答案偏大。正确的理解方式是一旦某个任务的所有前置任务都完成了这个任务就立刻可以开始而且不需要排队。所有任务都自动“一人负责一件事”互不干扰。2.3 最终答案不是最后一个任务的完成时间还有一个细节要注意输入给出的任务编号顺序并一定是拓扑顺序最后一个任务也不一定是整条依赖链的终点。有可能任务7是最早开始的但最终卡进度的却是任务2所在的链路。所以最终答案不是dp[N]最后一项任务的完成时间而是max(dp[1] ... dp[N])也就是所有任务里结束时间最晚的那一个。这个坑我在第一次写代码时也踩过后面在“常见问题”部分会再细说。3. 核心思路一拓扑排序 动态规划最正统的解法3.1 为什么需要拓扑排序现在我们明确了任务之间是一种“先做 A 才能做 B”的偏序关系这种关系如果用图来表示每个任务是节点每个依赖关系是一条有向边——从被依赖的任务指向需要它的任务——那么整张图一定是一个 DAG有向无环图。为什么一定无环道理很简单如果 A 依赖 BB 又依赖 A这两个任务就永远无法开始这在现实里是个死锁。题目既然给出了可行解就保证了图中不存在环。在 DAG 上做动态规划最自然的遍历顺序就是拓扑序。只有保证遍历到某个节点时它所有的前置节点都已经处理完毕这个节点的 dp 值才能一次性算对不用回头反复更新。你可以把拓扑排序理解成“给任务排一个合理的开工顺序表”排在前面的一定是那些不依赖别人的任务排在后面的则是在它的所有前置任务之后。3.2 状态定义和转移方程定义dp[i] 完成到任务 i 为止最早能结束的时间注意这个“最早能结束的时间”包含前置任务的时间而不只是任务 i 本身的工作时长。那么任务 i 最早能开始的时间是它所有前置任务 t 的dp[t]的最大值start[i] max(dp[j]) // j 是 i 的所有前置任务因为所有前置都做完i 才能开工而“都做完”等于最慢的那个前置任务做完。于是dp[i] start[i] cost[i] max(dp[j]) cost[i]最后答案ans max(dp[1], dp[2], ..., dp[N])这跟“关键路径”其实是同一个模型把每个任务看成一条有向边边的权值就是任务耗时求从任意源点出发到任意汇点的最长路径。3.3 代码实现Kahn 拓扑序 DP这里我给出一个用邻接表存图、Kahn 算法求拓扑序后做 DP 的完整实现。#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint g[MAXN]; // 邻接表记录每个节点的后继 int indeg[MAXN]; // 入度 int cost[MAXN]; // 每个任务花费的时间 int dp[MAXN]; // 最早完成时间 int main() { int n; cin n; for (int i 1; i n; i) { int id, c, m; cin id c m; cost[id] c; for (int j 0; j m; j) { int pre; cin pre; g[pre].push_back(id); // 前置任务 - 当前任务 indeg[id]; } // 行末的 0 不需要读入因为 m 已经告诉了我们前置任务的个数 } queueint q; for (int i 1; i n; i) { if (indeg[i] 0) { q.push(i); dp[i] cost[i]; // 没有前置任务最早开始就是 0完成时间就是自身耗时 } } while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { indeg[v]--; dp[v] max(dp[v], dp[u] cost[v]); if (indeg[v] 0) { q.push(v); } } } int ans 0; for (int i 1; i n; i) { ans max(ans, dp[i]); } cout ans endl; return 0; }代码核心就两个地方每遇到一条边pre - id就把id的入度加 1。入度为 0 的节点是“当前就能开工的任务”先把它们的 dp 值初始化为自身耗时。在拓扑排序的过程中每处理完一个节点 u就尝试用它去更新所有后继 v 的 dp 值。dp[u] cost[v]表示“通过 u 这条链路v 最早能什么时候完成”。因为 v 可能有多个前置所以要取最大值。这个“边更新边取最大值”的做法本质上是在做 DAG 上的最长路 DP只不过借助拓扑排序保证了更新的顺序。3.4 为什么要在出队时才更新 dp 而不是在入队时有一个非常容易搞混的点到底是在入队前更新还是在出队时更新我的代码是在while循环内部、把u的后继全部扫描一遍的时候更新dp[v]。当indeg[v]减到 0 时说明 v 的所有前置都已经处理完了这时dp[v]已经被所有前置节点更新过了可以安全入队。换一种思路如果你在某个节点入队之后再去更新它的dp可能会漏掉某些边因为以这个节点为前置的那些节点还没有被遍历到。所以更新动作要发生在遍历边的时候而不是节点入队的时候这一点初学者一定要想明白。4. 核心思路二记忆化搜索什么都不用管直接 DFS4.1 跟拓扑排序相比记忆化搜索的直觉更暴力如果你觉得拓扑排序还得维护入度、写队列思路稍微绕了一点那记忆化搜索是另一条更容易“一拍脑袋想到”的路线。想法非常直接想知道任务 i 最早什么时候完成就需要知道它所有前置任务最早什么时候完成想知道前置任务最早什么时候完成又要知道前置的前置……递归到没有前置的任务时返回它自身的耗时即可。这种从“当前任务”向上追溯“依赖链”的过程就是深度优先搜索。为了避免同一个任务被反复计算有的图里依赖关系会汇总一个任务可能是很多任务的共同前置用一个dp[]数组保存已经算好的结果也就是记忆化。4.2 代码实现DFS memo#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint pre[MAXN]; // 存储每个任务的前置任务 int cost[MAXN]; int dp[MAXN]; int dfs(int u) { if (dp[u] ! -1) return dp[u]; // 已经算过直接返回 int res 0; for (int v : pre[u]) { res max(res, dfs(v)); // 所有前置里最晚完成的时间 } return dp[u] res cost[u]; // 前置最晚 自己耗时 } int main() { int n; cin n; for (int i 1; i n; i) { int id, c, m; cin id c m; cost[id] c; for (int j 0; j m; j) { int preTask; cin preTask; pre[id].push_back(preTask); } } memset(dp, -1, sizeof(dp)); int ans 0; for (int i 1; i n; i) { ans max(ans, dfs(i)); } cout ans endl; return 0; }这个代码可能比拓扑排序的还好理解先把输入里的“前置关系”存下来然后从每个任务都跑一次dfs(i)求它最早的完成时间。因为记忆化数组的存在所有任务实际只会被真正计算一次每个前置关系也只会被扫描一次所以复杂度同样接近O(N M)。4.3 记忆化搜索和拓扑排序本质上是一回事有意思的是两种方法看着完全不一样一个迭代一个递归一个正向扫描一个反向追溯但它们的核心逻辑完全相同拓扑排序从没有前置的任务开始一层一层向后推。记忆化搜索从最后一个任务往前递归碰到没有前置的任务时返回。它们的关系就像“自底向上的 DP”和“自顶向下的 DP”的关系状态定义一样转移方程一样只是遍历方向不同。如果你的代码在递归时爆栈了可以考虑换成拓扑排序的写法如果拓扑排序写起来容易乱那就先用记忆化搜索拿分这两种方法在比赛中都是安全且优美的解法。我个人实际做题时如果时间紧张或者题目比较绕会优先写记忆化搜索因为不需要额外处理入度数组也不容易写错初始化的逻辑。只有在递归层数可能很深比如 N 到达 10 万以上时才考虑拓扑排序防止调用栈溢出。5. 隐藏的简单解法因为输入顺序这题可以 O(N) 直接贪心5.1 为什么可以“边读入边算”这题还有一个比较少被提到的性质USACO 这道题保证了每个任务的前置任务编号一定小于当前任务编号。也就是说输入给出的顺序本身就是拓扑序的某种体现——前置任务的编号永远比当前任务小。利用这个性质我们可以做到真正的 O(N)甚至不需要建图、不需要递归。处理到某个任务时它依赖的所有任务都已经在前面的步骤处理过了所以它的 dp 值可以直接从已经算好的dp[前置编号]中取最大值。有人说这样算不算“投机取巧”我觉得不算。很多 look 简单的问题正因为输入数据给了特殊性质才可以用更简单的方法解。竞赛中利用题目隐含条件简化问题本来就是非常核心的能力。5.2 代码实现一行核心转移#include bits/stdc.h using namespace std; const int MAXN 10005; int dp[MAXN]; int main() { int n; cin n; int ans 0; for (int i 1; i n; i) { int id, c, m; cin id c m; int mx 0; for (int j 0; j m; j) { int pre; cin pre; mx max(mx, dp[pre]); } dp[id] mx c; ans max(ans, dp[id]); } cout ans endl; return 0; }注意mx的初始值是 0因为dp[pre]肯定最小也是cost[pre]而耗时是正整数所以max(mx, dp[pre])不会出错。整个程序的时间复杂度是 O(N M)其中 M 是所有任务的前置关系总数。空间复杂度 O(N)。这已经是最优的了因为你至少要把每条依赖边读进来才能算出正确答案。5.3 这种“边读边算”依赖什么条件敲黑板这种写法依赖“前置任务编号必然小于当前任务编号”这一输入性质。在我印象里USACO 的这道题确实如此但如果你遇到的变体题没有明确说明这一点千万不要贸然使用这种写法。比如输入第一行是编号 3 的任务编号 1 的任务在后面才出现那你就必须在建图之后做拓扑排序或者记忆化搜索否则dp[pre]还是 0算出来的结果就是错的。判断是否能用这个技巧最快的方法就是看样例输入里每行前置任务的编号是不是都小于当前任务编号。如果题目描述里没有写可以用数据范围反推如果 N 特别大大到没法建图那基本上就是故意设计成可以用这种简化写法的。5.4 三种写法复杂度对比解法时间复杂度空间复杂度代码量适用条件拓扑排序 DPO(N M)O(N M)中等任意 DAG记忆化搜索O(N M)O(N M)较少任意 DAG递归深度可控输入顺序 DPO(N M)O(N)最少前置编号小于当前编号三者时间复杂度其实相同都是线性级别它们在竞赛中都是满分解法。区别只在于写题时的思维负担和实际代码量。如果你在正式比赛中遇到这道题我建议如果只是想要 AC而且确定前置编号有序直接写第三种省时省力如果是为了学习算法建议把第一种和第二种都手写一遍因为它们才是可迁移到“没有特殊性质”的通用解法。6. 从 P1113 到整个算法思想DAG 上的 DP 模型6.1 为什么说这是一类题的母题很多人刷题只满足于“AC 了”但我一直建议把一道经典题目的思想抽出来因为它能帮你解锁一大片题目。P1113 恰恰就是“DAG 上最长路 / 关键路径”这一类题中最平易近人的模板题。我们在题目里做的事情放到现实世界中就是项目管理里的关键路径分析。一个大型项目有成千上万个任务每个任务有预估工期任务之间有先后依赖项目经理最关心的就是“所有任务最快什么时候能完成”“哪条任务链是无论如何都压缩不了工期的瓶颈”。这个“瓶颈链”就是关键路径。关键路径上的任何任务推迟整个项目都会推迟关键路径之外的任务有一定浮动时间晚几天不影响整体进度。如果你把 P1113 的概念稍微扩展一下每个任务的耗时换成“权重”依赖关系换成“有向边”最后求的max(dp[i])换成“汇点的 dp 值”那就是标准的关键路径法Critical Path Method, CPM。6.2 在竞赛题里常见的变式基于 DAG 上 DP 的模型可以演变出很多题目我帮你梳理几个常见方向刷题时遇到能立刻反应过来求关键路径上的具体节点/边除了算 dp 值还要反向记录“是从哪个前置转移过来的”最后像回溯最短路径一样把关键路径还原出来增加“最晚开始时间”这要计算任务在不影响整体工期的情况下最晚可以什么时候开始需要两次 DP一次正推最早完成时间一次倒推最晚开始时间多条依赖路径的权重总和比如问每个任务最早开始时间的异或和之类的本质还是同一个转移方程只是最后的汇总方式变了加上图的边权而不是点权有些题把耗时定义在“前置任务到当前任务”这条边上而不是任务本身那么dp转移就变成dp[v] max(dp[v], dp[u] edgeWeight(u, v))嵌套分层图比如每个节点访问一次后不能再访问或者每种颜色最多选中几个这就要在 DAG 上配合状态压缩 DP 来做。这些题看似五花八门核心却都是同一个东西在 DAG 上保证遍历顺序的前提下用已经算好的局部最优值去更新后继节点。如果你能把 P1113 的三种写法都吃透再遇到这些变式你至少不会卡在“不知道用什么算法”这一步而是能快速判断出“这是 DAG 上的 DP”并开始设计状态。6.3 和“树形 DP”的关系P1113 的依赖关系如果保证每个任务最多只有一个前置任务那这张图就退化成一棵树或者森林问题就变成了“求树根到叶子节点的最大路径和”。有些新手看到 P1113 的题意第一反应是“这题是不是树形 DP”其实是两种题型的交融树形 DP 是 DAG 上 DP 的一种特殊情况。不过 P1113 的依赖关系是“多个前置可以指向同一个任务”边的方向也可能更复杂所以它不完全是树。理解这个关系有个好处当你遇到一道“任务依赖”题先画图如果每个节点只有唯一父节点那就是树如果有多个前置那就是普通 DAG。前者可以用树形 DP 的套路做后者用拓扑排序 DP 或者记忆化搜索更稳。7. 完整实操的一遍从读题到 AC 的思维过程7.1 第一步千万别急着写代码先手推样例我看到题目第一件事从来不是直接上代码而是在草稿纸上把样例的依赖关系画出来。这里我带你完整走一遍任务1耗时5无依赖。 任务2耗时2依赖1。 任务3耗时3依赖1、2。 任务4耗时6依赖1。 任务5耗时1依赖4。 任务6耗时8依赖2、4。 任务7耗时4依赖3、5、6。把图画出来1 指向 2、3、42 指向 3、64 指向 5、63、5、6 指向 7。现在从 1 开始推dp[1] 5 dp[2] dp[1] 2 7 dp[3] max(dp[1], dp[2]) 3 max(5, 7) 3 10 dp[4] dp[1] 6 11 dp[5] dp[4] 1 12 dp[6] max(dp[2], dp[4]) 8 max(7, 11) 8 19 dp[7] max(dp[3], dp[5], dp[6]) 4 max(10, 12, 19) 4 23最大的是 dp[7] 23所以答案是 23。你如果用代码跑一遍样例输出确实就是 23。手推一遍不仅能验证你对题意的理解还能帮你确认最终的答案到底取的是最后一个 dp 值还是全体的最大值。在这个样例里最后一个任务是 7dp[7] 恰好也是最大值但这一题的隐藏测试点里很可能不是这样所以还是不能直接输出dp[n]。7.2 第二步选择解法并考虑边界条件如果你是在训练赛里时间充足的话我建议把三种写法都在本地跑一遍对比一下结果是否一致这样能最大程度避免“方法本身写错但样例恰好过了”的尴尬。需要注意的边界条件N 1 时只有任务 1耗时 c答案就是 c所有任务都没有前置任务时答案是所有任务耗时的最大值因为它们可以全部并行前置关系特别多比如每个任务都依赖前面所有任务时注意mx初始化为 0 不能省否则会得到负数时间类型的输入可能有 0 耗时任务吗按理说耗时是正整数但如果出题人没有说明你在写法上也不需要特别处理0 耗时天然兼容。7.3 第三步写代码时注意输入行的“行末 0”前面我提过输入每行最后有一个 0但这个 0 只是终止标记不代表前置任务编号。在cin id c m;之后你直接循环 m 次读前置任务编号就行那个 0 不用读入因为它已经在 m 次循环之外了。有些新手会这样写while (cin x x ! 0) { ... }然后发现读入顺序乱了原因就在于你一边用 m 控制循环一边又试图用 0 作为循环终止条件两个条件叠加反而互相干扰。这题的正确姿势是以 m 为准循环0 是留给那些没有前置的任务用的m 0 时for循环直接不执行行尾的 0 自然被略过。8. 常见问题与排查技巧实录8.1 输出结果比答案小如果你跑出来的结果偏小大概率是dp值的更新顺序有问题。典型场景你用的是“输入顺序 DP”但题目没有明确保证前置编号小于当前编号。假设某个任务的前置任务编号比它大按输入顺序处理时前置还没算出来它的dp值就是 0导致当前任务的dp算小了。排查方法很简单随机生成几组数据把边的关系打乱看三种写法的结果是否一致。如果不一致立即转用拓扑排序或记忆化搜索。比赛时如果时间紧张直接改写法比一行一行 debug 快得多。另一个可能原因是最终答案取错了地方。只输出dp[N]而忘了取全部任务的最大值也会得到偏小的答案。这种错误样例经常看不出来因为样例里最后一个任务往往刚好是关键路径终点但隐藏数据里不是。8.2 输出结果比答案大结果偏大通常是因为你忽略了“并行执行”这个条件。比如说你把所有任务的耗时直接累加了或者你错误地认为每个任务必须等上一个任务完成才开始这等于把 DAG 当成了一条链。回想一下题目样例任务5耗时1依赖任务4任务6耗时8依赖任务2和4。任务5和6之间没有依赖关系它们完全可以同时进行如果你把它们当成先后执行结果就会偏大。这类错误从样例数据里最容易发现因为样例专门设计成了有并行分支的结构就是为了考察这个点。如果你能推出样例的 23说明你已经理解并行如果不能返回到第 2 节重新看一眼“并行执行”那一段。8.3 递归爆栈了怎么办记忆化搜索写起来舒服但如果任务数量极大且依赖链很深比如 N 100000、每个任务都依赖前一个任务那递归深度可能会超过默认栈限制。这时候你可以换用拓扑排序 DP 的迭代写法或者手动把递归改成栈模拟不过没有必要直接换写法是最省事的也可以用迭代加深等技巧但这题不需要。C 在部分 OJ 上默认栈空间比较小如果你在做题时发现本地跑没问题、提交就 RE多半就是爆栈。判断是不是爆栈可以在本地把 N 调到 100000 跑一条长链试试如果 RE那就换迭代写法。8.4 常见问题速查表症状可能原因解决方法答案偏小依赖关系未按拓扑序处理改用拓扑排序或记忆化搜索答案偏小直接输出了 dp[N] 而不是全局最大值遍历所有任务取 max答案偏大把可并行任务当成了串行执行检查转移方程里是否取max而不是累加答案偏大重复累加了前置任务的耗时检查dp[v] max(dp[v], dp[u] cost[v])是否写成了dp[v] dp[u] cost[v]输入错乱读入了行末的 0 当作前置任务用 m 控制循环0 不处理RE本地正常提交挂递归层数过深改用拓扑排序迭代写法8.5 一个调试小技巧打印依赖链最后分享一个我常用的调式方法。比赛时如果答案不对我经常会写一个辅助函数把每个任务的 dp 值打印出来然后手动对照图检查for (int i 1; i n; i) { cerr dp[ i ] dp[i] endl; }这样一眼就能看出是哪个任务的 dp 算错了再顺着它的前置任务往前查很快就能找到问题。特别是遇到“所有样例测试点过了但 WA”的情况强制自己打印中间结果几乎是最快的定位方式。9. 写在最后的几点体会P1113 是我当年在洛谷上认真刷的第一批图论题之一当时觉得“杂务”这个题面特别接地气后来做完才发现里面藏着一整个工程调度模型。现在回头再看这道题真正的价值不在“AC”本身而在于帮你建立一种直觉遇到“有依赖关系的调度问题”第一步就是画 DAG第二步就是顺着拓扑序做 DP第三步就是想想能不能利用题目隐含性质简化实现。如果你刚接触这类题我建议把三种解法都写在同一个编译器里跑一遍互相交叉验证。这个过程本身就是对“同一个问题的不同解法”最好的理解方式。等以后刷到更复杂的 DAG 题比如带权边、多约束条件、路径还原你会发现底子就是这么打下来的。我个人现在的习惯是先在草稿纸上把样例手推一遍确认答案无误后再根据题目性质选择最简单的写法。如果确定输入顺序就是拓扑序那就直接边读边算五分钟解决战斗。如果输入顺序不确定就直接上记忆化搜索。只有 N 特别大导致递归可能爆栈时才用拓扑排序的迭代版本。把这个思路固定下来你在赛场上遇到这类题就不会慌。这道题后续还可以怎么扩展如果你感兴趣可以把“求最早完成时间”改成“按最晚完成时间排任务”或者把“一个任务可以并行执行”改成“最多同时执行 K 个任务”那就是另一道更复杂也更贴近真实生活的题目了。从 P1113 出发你可以延展出一整套关于任务调度、关键路径、资源约束规划的认知这远比刷过一道题本身有价值得多。