C++任务编排系统：拓扑排序+动态规划求解华为OD真题

最近刷到华为OD机试C卷的真题回忆看到《任务编排系统》这个题目名我第一反应是“完了系统设计题”实际上这种带业务背景的题最唬人剥掉外壳之后就是一道非常经典的图论题有依赖关系的任务调度。华为OD机试C选手遇到它核心要掌握的就是拓扑排序 动态规划最长路径模型。这篇文章我会用C给出ACM模式的完整解法从题目还原、状态定义、完整代码到考场易错点全部按可以直接照用的标准来写。如果你正在用C刷OD机试或者想在C卷里稳定拿下图论题这篇值得花十分钟读完而不是只收藏。1. 题目模型还原别被“编排”两个字带偏1.1 我记忆中的题目长这样华为OD机试这类题目一般不会给特别复杂的业务背景核心就是一个任务依赖模型。回忆版的题目大致如下系统里有 N 个任务编号从 0 到 N-1。每个任务有自己的执行耗时w[i]同时可能依赖若干个前置任务。只有当一个任务的所有前置任务都执行完成后这个任务才能开始执行。系统中有足够多的执行单元也就是说只要依赖条件满足任务之间可以无限并行不需要考虑机器数量限制。现在给出每个任务的耗时和依赖关系要求计算完成全部任务所需的最短时间输出一种可行的任务执行顺序按任务开始时间从早到晚输出如果开始时间相同按编号从小到大。输入保证依赖关系不会成环。输入格式大致是N w[0] k 前置任务编号... w[1] k 前置任务编号... ...比如这样一组输入4 5 0 3 0 4 1 0 6 2 0 1第0个任务耗时5无前置第1个任务耗时3无前置第2个任务耗时4依赖任务0第3个任务耗时6依赖任务0和1。那最短完成时间应该是11一种合法的执行顺序是0 1 2 3。为什么是11因为任务0和任务1可以同时开始任务2最早要到第5秒开始任务3最早也要等任务0完成第5秒和任务1完成第3秒的交集也就是第5秒开始所以任务3在第11秒结束这就是整批任务的最短完成时间。1.2 做题前先抓住三个关键点这类题表面上叫“任务编排”实际考的就是有向无环图DAG上的动态规划。要快速做对至少要抓住三点依赖关系是有方向的前置任务完成后后继任务才能开始。所以能建出一张DAG并且可以拓扑排序。执行单元无限多不存在资源竞争这意味着总完成时间只取决于依赖链上累计耗时最大的那一条路径而不是把所有任务的耗时加起来。这就是关键路径思想。每个任务的最早开始时间不是由某一个前置决定而是由所有前置任务中最晚完成的那一个决定。因此转移方程必须取最大值不是求和也不是取平均值。很多人看到“任务编排”就以为要模拟队列、调度器、多线程越做越复杂。实际上只要识别出“前置依赖 最短完成时间”这个组合就应该立刻想到图论模型代码量并不大。2. 核心算法为什么是拓扑排序 动态规划2.1 从暴力递归到拓扑序先别急着写代码我们来推一推朴素思路。如果不用任何技巧最粗暴的做法是DFS求每个任务的最早开始时间递归去查它所有前置任务的最早开始时间然后取最大值。对于小数据这能跑通但有两个问题。第一个问题是重复计算。一个任务可能被多个后继依赖每次递归都可能把同一组前置重新算一遍当依赖关系复杂时时间复杂度会指数级增长。第二个问题是递归深度。万一题目里有一条很长的链式依赖N到几万甚至几十万DFS递归很可能直接爆栈。所以我们需要一个稳定的计算顺序保证每个任务一旦计算它的所有前置任务都已经算完了。这不就是拓扑排序吗拓扑排序的结果是如果存在边u - v那么u一定排在v前面。我们按这个顺序从前往后递推每个任务只计算一次复杂度能做到 O(N E)也就是点和边的总数。在机试环境下这是最稳妥的方案。2.2 状态定义与转移方程设early[i]表示任务i的最早开始时间。对于没有前置任务的任务可以一开始就执行所以early[i] 0对于有前置任务的任务它必须等所有前置任务都完成。因此early[v] max(early[v], early[u] w[u])这里u是v的一个前置任务w[u]是任务u的耗时。含义是任务v最早开始时间不能早于u的完成时间而u的完成时间就是early[u] w[u]。因为v可能有多个前置所以要不断取最大值。最终所有任务完成的最短时间就是ans max(early[i] w[i])也就是所有任务中最晚的结束时间。2.3 Kahn算法和DP怎么结合Kahn算法是拓扑排序的经典实现先统计每个节点的入度把所有入度为0的节点放入队列。然后循环取队首节点u遍历u的所有后继v将v的入度减1如果v的入度变成0说明v的所有前置任务都处理完了可以入队。这个过程天然适合做DP。关键在于更新时机当u从队列中弹出的时候early[u]已经是最终值不会再被改大。此时用u去更新它所有后继v的early[v]是安全的。如果u还没被确定就更新后面可能有更晚的前置让early[v]变大就会漏算。所以整体思路是拓扑排序提供计算顺序DP负责在正确时机做状态转移。两者是一体的不是两段无关的逻辑。3. C 完整实现ACM模式全流程代码3.1 建图输入技巧华为OD机试的C题一般是ACM模式需要自己写输入输出。先讲建图。依赖关系是pre - i意思是前置任务pre完成后任务i才能开始。所以我们建邻接表时存的是有向边pre指向ivectorvectorint nxt(N); vectorint indeg(N, 0);读入每一条前置依赖时做两件事nxt[pre].push_back(i); indeg[i];一个是记录后继一个是为后继累加入度。这两个操作必须同时做漏掉任何一个都会导致拓扑排序失败。这里不需要存 “每个任务的前置列表”因为DP时我们只需要从已确定的任务往后推不需要回头找前置。前置信息只用来处理入度。3.2 完整可运行代码下面是我在本地测试过可以直接跑的完整C代码使用C11以上标准编译#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; // 支持多组测试样例读到EOF为止 while (cin N) { vectorlong long w(N, 0); vectorvectorint nxt(N); vectorint indeg(N, 0); for (int i 0; i N; i) { cin w[i]; int k; cin k; for (int j 0; j k; j) { int pre; cin pre; // pre 是 i 的前置任务建边 pre - i nxt[pre].push_back(i); indeg[i]; } } vectorlong long early(N, 0); queueint q; // 所有入度为0的任务可以立刻开始 for (int i 0; i N; i) { if (indeg[i] 0) { q.push(i); } } int visited 0; // 拓扑排序 DP while (!q.empty()) { int u q.front(); q.pop(); visited; for (int v : nxt[u]) { // 用 u 的完成时间更新 v 的最早开始时间 long long finishU early[u] w[u]; if (finishU early[v]) { early[v] finishU; } indeg[v]--; if (indeg[v] 0) { q.push(v); } } } // 题目保证无环但判环能让代码更健壮 if (visited ! N) { cout Cycle endl; continue; } // 计算总耗时 long long ans 0; for (int i 0; i N; i) { ans max(ans, early[i] w[i]); } cout ans endl; // 输出执行顺序按最早开始时间升序相同则按编号升序 vectorint order(N); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [](int a, int b) { if (early[a] ! early[b]) return early[a] early[b]; return a b; }); for (int i 0; i N; i) { if (i) cout ; cout order[i]; } cout endl; } return 0; }3.3 三处容易忽略的细节第一耗时变量要用long long。题目单个任务耗时可能不大但任务数量多、依赖链很长时累加结果可能超过int上限。机试平台上数据范围有时候不写在表面用long long最稳。第二入度为0的节点入队时要一次性全部入队不能只入队一个。因为可能存在多个可以同时开始的任务漏掉一个就会让拓扑排序访问不到部分节点进而输出错误。第三early数组初始化为0是符合语义的。任务可以在第0秒开始所以没有前置任务的任务开始时间就是0。有些同学会习惯性初始化成-1或者INF反而让更新逻辑变复杂。4. 手动跑通样例再验证边界4.1 常规样例推导用前面那组输入4 5 0 3 0 4 1 0 6 2 0 1程序执行过程如下初始入度为0的是任务0和任务1它们进入队列。弹出任务0early[0]0更新任务2的early[2] max(0, 05)5任务2入度变成0更新任务3的early[3] max(0, 05)5任务3入度原本是2现在变成1。弹出任务1early[1]0更新任务3的early[3] max(5, 03)5任务3入度变成0入队。弹出任务2early[2]5没有后继。弹出任务3early[3]5没有后继。最终ans max(5, 3, 9, 11) 11。输出顺序按early排序任务0和任务1的 early 都是0按编号任务0在前任务2和任务3的 early 都是5按编号任务2在前。所以输出0 1 2 3。这个顺序是合法的因为任务3依赖任务0和1它排在两者之后任务2依赖任务0也排在任务0之后。4.2 几个特殊用例我整理了几个值得自己测一遍的边界场景场景输入特点预期结果单任务N1无依赖总耗时等于该任务耗时顺序输出0长链式依赖0-1-2-3 依次依赖总耗时等于所有耗时之和顺序必须严格递增完全并行所有任务入度为0总耗时等于最大单个任务耗时顺序可按编号输出有环依赖0依赖11依赖0程序能通过 visited ! N 检测出环建议每个人都在本地把这几个用例跑一遍。单任务和完全并行能验证初始化是否正确长链式依赖能验证更新逻辑是否正确有环虽然题目不涉及但能让你对拓扑排序的判环能力更有信心。4.3 输出顺序的小坑如果要输出执行顺序我最推荐的做法是先算完early再对任务编号排序而不是直接输出队列的出队顺序。原因是队列出队顺序依赖入队的先后虽然它一定是一个合法的拓扑序但题目如果要求“按开始时间从早到晚”直接用队列出队顺序可能不满足。举个例子两个无依赖任务任务0耗时100任务1耗时1。如果输入顺序是先读任务0后读任务1队列出队顺序是0、1但任务1明显在第1秒就结束了任务0要到第100秒才结束按开始时间排序应该是0、1开始时间都是0所以这里没问题。但如果要求按完成时间排序队列出队顺序就会错。所以统一做法是对early排序这样语义最清晰也不依赖入队顺序。5. 考场上最容易翻车的四个地方5.1 更新后继的时机错位这是这题最大的坑。有些同学会把更新后继的代码写在 “入度减到0、节点入队” 的时候写成这样if (--indeg[v] 0) { early[v] max(early[v], early[u] w[u]); // 错误 q.push(v); }看起来好像差不多实际上问题很大。u只是让v的入度减到0的最后一个前置但不代表u是v的所有前置中完成时间最晚的一个。如果在这个位置只更新一次可能把之前其他前置给的更大的early[v]给覆盖掉或者漏掉对early[v]的累加。正确做法是遍历每条边时都更新early[v]不管v是否入队。因为一个任务的所有前置都会各自更新它一次最后取到的最大值就是我们需要的结果。等到入度减为0时early[v]已经包含所有前置的贡献这时再入队就能保证v在出队时带着正确的开始时间。5.2 依赖方向搞反读入时题目给的是一行里k个前置任务编号。要建pre - i不是i - pre。方向反了会导致两种情况一是刚读入时indeg统计错二是拓扑排序结果完全颠倒。我建议每次读入依赖时在草稿纸上画一下箭头前置任务指向当前任务。只要箭头方向画对邻接表就不会写错。5.3 多组样例容器没清空我的代码用while (cin N)支持多组样例这是一种常见的机试写法。如果你遇到的是多组输入容器w、nxt、indeg、early必须在循环内定义这样每组数据都是全新的。如果定义在循环外处理完一组后要手动clear()否则残留数据会让下一组计算错。如果题目明确说只包含一组测试数据不用多组写法也可以。但从稳妥角度很多OD机试题面并不会强调“单组”写多组兼容不会扣分。5.4 输出顺序用了拓扑序而不是开始时间序如果题目只要求输出任意一种可行执行顺序拓扑序可以直接用。但如果要求按开始时间从早到晚就必须像我代码里那样对early排序。考场上看清输出要求再决定要不要排序不然很容易丢掉这部分分数。6. 从OD真题延伸到实际调度模型6.1 变体如果限制机器数量怎么办这道题能无限并行是因为它退化成DAG最长路问题。但真实世界的任务编排系统通常不会无限并行比如只有M台机器每台机器同一时刻只能跑一个任务。那问题就从“求最长路径”变成了“带资源约束的调度问题”需要用贪心加优先队列来解。常见思路是先算出每个任务的最早开始时间再把所有可执行任务放入优先队列每次选择完成时间最早的空闲机器来执行当前最早开始的任务同时维护机器的空闲时间。算法复杂度和正确性都高一个档次。如果考试时遇到“机器数量有限”一定要换思路不能直接用这题的代码。6.2 快速识别这类题的两条经验我刷OD题时总结了一条粗鲁但有效的判断方法看到“依赖”“前置”“先后顺序”“拓扑”这些词优先想拓扑排序看到“最短完成时间”“最早开始时间”优先想DAG最长路。如果题目同时要求 “判断能否完成”则大概率是拓扑排序判环。如果题目给的是“有向图”且保证无环那基本就是给每个节点算最长路径。这个套路覆盖了OD机试里大部分图论题。6.3 现场做题节奏遇到这种题我最建议的节奏是先花两三分钟在草稿纸上画样例依赖图确认方向然后列出状态方程early[v] max(early[v], early[u] w[u])最后再动键盘。不要一上来就写队列和邻接表思路没顺的时候越写越乱。如果考试时发现时间不够优先保证第一问总耗时输出正确第二问输出顺序只要是一个合法拓扑序通常也能拿到部分分数没必要为了“按开始时间排序”这个要求卡太久。我个人做这类题最大的体会是题目名字越复杂考点往往越基础。所谓“任务编排系统”拆开就是“Kahn拓扑排序 最长路径DP”你只要把队列更新时机想清楚代码半小时内一定能写出来。备考OD的朋友不妨把这道题作为图论专题的入门例题反复练几遍把它练成肌肉记忆C卷考场上再看到类似题就不慌了。