# 异星工厂：科技树 ## 解法与署名出题人解法：删除已完成科技，以拓扑排序计算最早完成时刻。Codex（GPT-6）将递归的就绪传播改为显式队列，使用紧凑邻接表，保持原有建模与时间复杂度。程序：[std.cpp](std.cpp)。另有[三状态深度优先动态规划](solution-alternative-depth-first.zh.md)及[程序](alternative-depth-first.cpp)，直接沿依赖关系求值并检测环。它是同阶的不同遍历方案；队列算法仍为首选。 ## 已完成科技与依赖图已经完成的科技不再需要等待自己的依赖，也不会阻塞其他科技。因此，只有两个端点均未完成的依赖才需要保留。对于输入 $(u,v)$ ，在剩余图中建立边 $v\to u$ ，表示完成 $v$ 后向 $u$ 传递就绪信息。重复依赖可以保留：每条边分别计入入度，处理前驱时也分别减去一次。剩余自环不能消除，会被判定为无解。 ## 最早完成时刻设 $T(u)$ 为科技 $u$ 的最早完成时刻。对剩余图的结点有 $$T(u)=t_u+\max_{v\to u}T(v)$$ 没有前驱时最大值为零。维护每个结点的未处理入度。将所有入度为零的结点加入队列，初始完成时刻为自身耗时。弹出 $u$ 后，对每条边 $u\to v$ 执行 $$T(v)\gets\max\{T(v),T(u)+t_v\}$$ 并把 $v$ 的入度减一；减至零时加入队列。 ## 正确性与无解判定每项科技必须等待所有前驱完成，所以上式给出任何方案都无法突破的下界。无限并行允许每项科技在全部前驱完成后立即开始，因而也能达到该下界。按拓扑次序归纳，队列算法计算的全部完成时刻最优，最终答案是它们的最大值。若仍有未处理结点，则剩余有限有向图中存在环。环上第一个开始的科技必然仍有未完成的环内依赖，因此不存在这样的第一个科技，无法完成。这个论证也适用于全零耗时的环。反过来，无环图一定存在入度为零的结点，拓扑过程可以处理全部结点。 ## 复杂度与实现时间 $O(n+m)$ ，空间 $O(n+m)$ .使用显式队列可处理长度达 $n$ 的链而不消耗递归调用栈。邻接表使用 `Head` 、`To` 、`Next` 数组。设最大非负耗时为 $U$ ，可完成实例的答案至多 $nU$ ，当前范围可达 $10^{15}$ ，完成时刻使用 64 位整数。全部已完成时答案为零；无依赖时答案为剩余耗时的最大值。三状态方案同为 $O(n+m)$ ，沿依赖方向组织计算，适合使用每点“未访问／计算中／已完成”状态的实现。 ## 验证与运行独立事件模拟器逐次启动已就绪任务并推进至下一完成时刻，覆盖三结点有向图、自环、重复边、零耗时环和已完成科技。正式输入覆盖百万结点与两百万依赖。每题的 `tests/plan.json` 包含十份输入的固定种子和目的。编译程序后，可运行： ```text python tests/generate.py --out-dir --std ``` 省略 `--std` 只生成输入，`--case 01` 选择单份输入。独立验证脚本见 [check_r15.py](../../../tools/check_r15.py)。五轮交替计时与内存记录见[测量数据](../../../docs/benchmark-R15.json)，环境说明见[评测环境与性能](../../../docs/评测环境与性能.md)。有限测试与具体程序的计时不代替上面的证明，也不保证所有同阶实现都能在同一时限内通过。 ## 实测结果 | 程序 | 最慢用例中位时间 | 峰值工作集 | | --- | ---: | ---: | | 标程 | 0.447671 秒 | 43.34 MiB | | 补充程序 | 0.376580 秒 | 36.67 MiB | 参考时限为 1.0 秒。十份已测正式输入上，两份程序结果一致，均在该时限内完成。上述内存是包含进程开销的峰值工作集，时间与内存的最大值可能来自不同输入。