数据结构与算法 / 系统课时
综合题怎样从样例推模型
综合题怎样从样例推模型
综合图论题真正困难的往往不是实现某个算法,而是把题意连续翻译成“点、边、方向、权值和目标”。本节用一份完整例子演示如何从样例提出模型假设,再用约束和反例筛掉错误解释,最终落到可实现、可验证的算法上。
学习目标
- 从题意和样例中识别点、边、方向与权值分别代表什么
- 用数据规模和目标函数把候选模型收敛到合适的图算法
- 通过边界样例和手算结果验证建图方向与状态转移是否正确
先把题目翻译成关系
面对综合题,不要先搜索“像哪道模板题”。先问四个问题:题目中的对象是什么,两个对象为什么会发生关系,这个关系有没有方向,最终要求的是最短、最长、连通、匹配还是可行性。
例如题目描述一个项目:每个任务都有耗时,若给出依赖 u -> v,则任务 v 必须等 u 完成后才能开始;多个互不依赖的任务可以并行。要求所有任务完成的最短时间。
样例中若任务 1、2 都指向任务 3,就能观察到任务 3 必须等待两个前置任务,而不是任选一个完成即可。这提示我们:任务是点,依赖是有向边,任务耗时是点权,目标不是普通最短路,而是计算依赖链上的最长累计耗时。

用约束决定算法
假设任务数和依赖数都可能达到 。这时枚举所有执行顺序显然不可行,而每个点、每条边只处理常数次的 算法是合适目标。
如果题目保证依赖关系不存在环,那么“前置任务必须先完成”天然对应 DAG。拓扑排序可以保证处理任务 v 时,它的前驱已经得到最早完成时间;随后做一次动态规划即可。
设 finish[v] 表示任务 v 的最早完成时刻,任务自身耗时为 cost[v]。对每条依赖 u -> v,候选转移是:先等待 u 完成,再执行 v。因此应维护 v 的所有前驱完成时刻中的最大值,而不是最小值。
模型判断可以压缩成下面几项:
| 题目信号 | 建模结论 |
|---|---|
| 一个任务依赖另一个任务 | 有向边 |
| 多个前置条件必须全部满足 | 取所有前驱完成时间的最大值 |
| 任务自身有耗时 | 点权 |
| 保证依赖无环 | DAG,可拓扑处理 |
| 规模达到 | 优先考虑 |
把推导落实成可运行程序
下面固定一组样例:任务耗时分别为 2、4、3、5、2;依赖为 1 -> 3、2 -> 3、3 -> 4、3 -> 5。任务 1 和 2 可以并行,但任务 3 必须等待二者都结束,因此它最早在时刻 7 完成;随后任务 4 在时刻 12 完成。
from collections import deque
n = 5
cost = [0, 2, 4, 3, 5, 2]
edges = [(1, 3), (2, 3), (3, 4), (3, 5)]
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
# start[v] 保存任务 v 能开始的最早时刻。
start = [0] * (n + 1)
finish = [0] * (n + 1)
queue = deque(i for i in range(1, n + 1) if indegree[i] == 0)
processed = 0
while queue:
u = queue.popleft()
finish[u] = start[u] + cost[u]
processed += 1
for v in graph[u]:
# v 必须等待所有前驱,因此取前驱完成时刻的最大值。
start[v] = max(start[v], finish[u])
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
if processed != n:
raise ValueError("dependency graph contains a cycle")
print(max(finish[1:]))预期输出
12这段实现同时完成了建模验证:若最终处理点数少于 n,说明依赖中存在环,与“可以按前置关系完成全部任务”的假设冲突。实际题目若没有保证无环,这个检查就不能省略。
算法对每个任务和每条依赖各处理有限次,时间复杂度为 ,邻接表、入度和状态数组占用 空间。
用反例检查自己是不是建错了
综合题最容易错的地方往往不是代码,而是模型在样例上碰巧成立。提交前应主动构造会区分不同解释的小样例。
如果把“等待所有前驱”误写成取最小值,可以构造两个前置任务耗时分别为 1 和 100 的情况。后继任务显然不能在时刻 1 开始,所以必须取最大完成时刻。
如果把边方向反建为 v -> u,拓扑顺序仍可能存在,程序甚至可能正常结束,但含义已经变成“后继完成后才能执行前置任务”。检查一条只有两个任务的依赖就能立即发现方向错误。
还要测试没有依赖的多个任务。此时它们应全部从时刻 0 开始,总完成时间等于所有任务耗时的最大值,而不是耗时之和。这能检查自己是否错误地把“允许并行”建模成了串行路径。
从样例推模型的关键不是猜中某个算法名称,而是形成闭环:先把题意变成关系,用样例观察局部行为,再用约束筛选算法,最后用能击穿错误假设的反例验证。只要点、边、方向、权值和目标函数都能分别解释清楚,综合题通常就已经从“陌生题”变成了若干熟悉算法的组合。