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