企业官网建设流程全解析

最近刷到华为OD机试C卷的真题回忆，看到《任务编排系统》这个题目名，我第一反应是“完了，系统设计题？”实际上这种带业务背景的题最唬人，剥掉外壳之后就是一道非常经典的图论题：有依赖关系的任务调度。华为OD机试C++选手遇到它，核心要掌握的就是拓扑排序 + 动态规划（最长路径模型）。这篇文章我会用C++给出ACM模式的完整解法，从题目还原、状态定义、完整代码到考场易错点，全部按可以直接照用的标准来写。如果你正在用C++刷OD机试，或者想在C卷里稳定拿下图论题，这篇值得花十分钟读完，而不是只收藏。

1. 题目模型还原，别被“编排”两个字带偏

1.1 我记忆中的题目长这样

华为OD机试这类题目一般不会给特别复杂的业务背景，核心就是一个任务依赖模型。回忆版的题目大致如下：

系统里有 N 个任务，编号从 0 到 N-1。每个任务有自己的执行耗时w[i]，同时可能依赖若干个前置任务。只有当一个任务的所有前置任务都执行完成后，这个任务才能开始执行。系统中有足够多的执行单元，也就是说，只要依赖条件满足，任务之间可以无限并行，不需要考虑机器数量限制。

现在给出每个任务的耗时和依赖关系，要求计算：

1. 完成全部任务所需的最短时间；
2. 输出一种可行的任务执行顺序（按任务开始时间从早到晚输出；如果开始时间相同，按编号从小到大）。

输入保证依赖关系不会成环。

输入格式大致是：

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指向i：

vector<vector<int>> nxt(N); vector<int> indeg(N, 0);

读入每一条前置依赖时，做两件事：

nxt[pre].push_back(i); indeg[i]++;

一个是记录后继，一个是为后继累加入度。这两个操作必须同时做，漏掉任何一个都会导致拓扑排序失败。

这里不需要存 “每个任务的前置列表”，因为DP时我们只需要从已确定的任务往后推，不需要回头找前置。前置信息只用来处理入度。

3.2 完整可运行代码

下面是我在本地测试过可以直接跑的完整C++代码，使用C++11以上标准编译：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; // 支持多组测试样例，读到EOF为止 while (cin >> N) { vector<long long> w(N, 0); vector<vector<int>> nxt(N); vector<int> 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]++; } } vector<long long> early(N, 0); queue<int> 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; // 输出执行顺序：按最早开始时间升序，相同则按编号升序 vector<int> 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，它们进入队列。
• 弹出任务0，early[0]=0，更新任务2的early[2] = max(0, 0+5)=5，任务2入度变成0；更新任务3的early[3] = max(0, 0+5)=5，任务3入度原本是2，现在变成1。
• 弹出任务1，early[1]=0，更新任务3的early[3] = max(5, 0+3)=5，任务3入度变成0，入队。
• 弹出任务2，early[2]=5，没有后继。
• 弹出任务3，early[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 几个特殊用例

我整理了几个值得自己测一遍的边界场景：

建议每个人都在本地把这几个用例跑一遍。单任务和完全并行能验证初始化是否正确，长链式依赖能验证更新逻辑是否正确，有环虽然题目不涉及，但能让你对拓扑排序的判环能力更有信心。

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卷考场上再看到类似题就不慌了。