异星工厂：简单火车¶

解法与署名¶

首选出题人的“加入非正边，再做 Kruskal”解法，程序为 std.cpp。Codex（GPT-6）采用按大小合并和迭代路径压缩，整理自环、重边、空边集及 64 位费用累加。

补充程序 alternative.cpp将经典 Borůvka 算法应用于收缩后的连通分量，完整说明见按分量选择最轻出边。它作为不同合并策略的备用方案保留；首选程序按边排序，补充程序按轮扫描全部边。

负费用边必须全部选择：加入任何尚未选择的负边，既不会破坏连通性，又能严格减少费用，即使它是自环或形成环也一样。

零费用边全部加入也不增加费用。因此先累计所有 \(w_i\le0\) 的费用，并用并查集合并它们的端点。此时每个连通分量可以看作一个收缩后的顶点。

剩余边的费用都为正。若某个连通方案在分量之间仍包含环，删去环上的任意边会保持连通并降低费用。因此最优补充方案是收缩图的一棵最小生成树。

把所有正费用边按费用从小到大排序。若一条边的两端属于不同并查集分量，就选择它、累加费用并合并；否则跳过。

在每次选择时，这条边是某个当前分量割上的最轻可用边。若一棵最优生成树尚未含它，加入它形成环，环上必有另一条跨过该割的边，其费用不小于当前边。交换这两条边不会增大总费用。因此每次选择均可扩展为最优生成树。

处理结束后，若只剩一个分量，非正边费用加生成树费用就是最优答案；若还有多个分量，所有备选边都无法再连接它们，输出 bad idea .

设 \(\alpha(n)\) 为并查集分析中的反 Ackermann 函数。排序与并查集总时间为 \(O(n+m\log(m+1)+m\alpha(n))\) ，空间为 \(O(n+m)\) .这里给出包含建表和空边集的界。

费用绝对值之和至多 \(2\times10^{15}\) ，必须使用有符号 64 位整数。单个顶点仍可能有应选择的负自环；没有边时，只有 \(n=1\) 可行。正自环不会连接两个分量，自动被跳过。并查集使用迭代查找，合并前按集合大小选根。

固定种子的十份正式输入配方见 tests/plan.json .先自行编译程序，再运行：

python tests/generate.py --out-dir <output-directory> --std <compiled-program>

省略 --std 仅生成输入；--case 01 选择指定用例。小规模独立验证见 check_r16.py，范围校验见 validate_r16.py。五轮时间、内存、输入和程序哈希见测量记录。环境与校准方法见评测说明。

Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 -O2。两份程序在相同十份正式输入上交替运行五轮。时间取每个用例中位数的最大值，包含启动与输入输出；峰值工作集独立测量，包含运行时开销。

程序与算法	最慢中位数（秒）	峰值（MiB）	1.5 秒参考时限
非正边收缩与 Kruskal	0.710041	35.69	已测输入通过
非正边收缩与 Borůvka	0.747512	39.52	已测输入通过

时限由标程最慢中位数乘以 2，向上取整到 0.5 秒得到。原始轮次、输入、源码和程序哈希见测量记录。其他评测机需重新校准；这些测量只描述随附实现及已测输入。