数据结构与算法 / 系统课时

综合题怎样从样例推模型

综合题怎样从样例推模型

综合图论题真正困难的往往不是实现某个算法,而是把题意连续翻译成“点、边、方向、权值和目标”。本节用一份完整例子演示如何从样例提出模型假设,再用约束和反例筛掉错误解释,最终落到可实现、可验证的算法上。

学习目标

  • 从题意和样例中识别点、边、方向与权值分别代表什么
  • 用数据规模和目标函数把候选模型收敛到合适的图算法
  • 通过边界样例和手算结果验证建图方向与状态转移是否正确

先把题目翻译成关系

面对综合题,不要先搜索“像哪道模板题”。先问四个问题:题目中的对象是什么,两个对象为什么会发生关系,这个关系有没有方向,最终要求的是最短、最长、连通、匹配还是可行性。

例如题目描述一个项目:每个任务都有耗时,若给出依赖 u -> v,则任务 v 必须等 u 完成后才能开始;多个互不依赖的任务可以并行。要求所有任务完成的最短时间。

样例中若任务 1、2 都指向任务 3,就能观察到任务 3 必须等待两个前置任务,而不是任选一个完成即可。这提示我们:任务是点,依赖是有向边,任务耗时是点权,目标不是普通最短路,而是计算依赖链上的最长累计耗时。

从样例到算法的连续推导流程

用约束决定算法

假设任务数和依赖数都可能达到 2×1052\times10^5。这时枚举所有执行顺序显然不可行,而每个点、每条边只处理常数次的 O(n+m)O(n+m) 算法是合适目标。

如果题目保证依赖关系不存在环,那么“前置任务必须先完成”天然对应 DAG。拓扑排序可以保证处理任务 v 时,它的前驱已经得到最早完成时间;随后做一次动态规划即可。

设 finish[v] 表示任务 v 的最早完成时刻,任务自身耗时为 cost[v]。对每条依赖 u -> v,候选转移是:先等待 u 完成,再执行 v。因此应维护 v 的所有前驱完成时刻中的最大值,而不是最小值。

模型判断可以压缩成下面几项:

题目信号 建模结论
一个任务依赖另一个任务 有向边
多个前置条件必须全部满足 取所有前驱完成时间的最大值
任务自身有耗时 点权
保证依赖无环 DAG,可拓扑处理
规模达到 2×1052\times10^5 优先考虑 O(n+m)O(n+m)

把推导落实成可运行程序

下面固定一组样例:任务耗时分别为 2、4、3、5、2;依赖为 1 -> 3、2 -> 3、3 -> 4、3 -> 5。任务 1 和 2 可以并行,但任务 3 必须等待二者都结束,因此它最早在时刻 7 完成;随后任务 4 在时刻 12 完成。

python
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:]))

预期输出

text
12

这段实现同时完成了建模验证:若最终处理点数少于 n,说明依赖中存在环,与“可以按前置关系完成全部任务”的假设冲突。实际题目若没有保证无环,这个检查就不能省略。

算法对每个任务和每条依赖各处理有限次,时间复杂度为 O(n+m)O(n+m),邻接表、入度和状态数组占用 O(n+m)O(n+m) 空间。

用反例检查自己是不是建错了

综合题最容易错的地方往往不是代码,而是模型在样例上碰巧成立。提交前应主动构造会区分不同解释的小样例。

如果把“等待所有前驱”误写成取最小值,可以构造两个前置任务耗时分别为 1 和 100 的情况。后继任务显然不能在时刻 1 开始,所以必须取最大完成时刻。

如果把边方向反建为 v -> u,拓扑顺序仍可能存在,程序甚至可能正常结束,但含义已经变成“后继完成后才能执行前置任务”。检查一条只有两个任务的依赖就能立即发现方向错误。

还要测试没有依赖的多个任务。此时它们应全部从时刻 0 开始,总完成时间等于所有任务耗时的最大值,而不是耗时之和。这能检查自己是否错误地把“允许并行”建模成了串行路径。

从样例推模型的关键不是猜中某个算法名称,而是形成闭环:先把题意变成关系,用样例观察局部行为,再用约束筛选算法,最后用能击穿错误假设的反例验证。只要点、边、方向、权值和目标函数都能分别解释清楚,综合题通常就已经从“陌生题”变成了若干熟悉算法的组合。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

综合题怎样从样例推模型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通