# 异星工厂：简单火车

## 解法与署名

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

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

## 先处理非正边

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

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

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

## Kruskal 与正确性

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

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

处理结束后，若只剩一个分量，非正边费用加生成树费用就是最优答案；若还有多个分量，所有备选边都无法再连接它们，输出 `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` .先自行编译程序，再运行：

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

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

## 实测结果

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

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 1.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [非正边收缩与 Kruskal](std.cpp) | 0.710041 | 35.69 | 已测输入通过 |
| [非正边收缩与 Borůvka](alternative.cpp) | 0.747512 | 39.52 | 已测输入通过 |

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