拓扑排序、AOE网与关键路径

考点定位

本课深化 拓扑排序、AOE网与关键路径。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

拓扑序存在当且仅当有向图无环。AOE网中，最早事件时间正向取最大，最迟事件时间逆向取最小；活动时差为0表示关键。

算法推演

Kahn算法维护入度0队列并删除出边；输出数少于顶点数则有环。关键路径工期是汇点最早时间，也等于关键活动持续时间之和。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

处理完的顶点不会再有来自未处理顶点的入边，否则它当时不可能入度为0。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：关键活动延误会直接影响工期；非关键活动只在超过总时差时影响工期。

随课应用

AOE网先执行3小时活动，再并行执行4小时和2小时活动，二者都结束后执行1小时活动。总工期是多少小时？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。