# 算法与复杂度

模型用两套 CSR 表示超边到顶点、顶点到超边的关联，构造时检查正权重、编号、重复针脚、总和与限额。模型拥有数据，内部关联数组保持隐藏。构造时间与空间均为 O(V + E + P)，P 为针脚总数。

初始起点按顶点权重降序、编号升序遍历，将顶点放到较轻且有容量的分区。其他起点用显式种子的 xorshift32 和 Fisher-Yates 洗牌。选解以独立复算的 cut-net 为准，平局保留先出现的解。所有起点失败后，用迭代深度优先装箱搜索做受限平衡修复。每次尝试一个顶点和分区组合消耗一个搜索节点。修复使用 O(V) 显式状态，不依赖随顶点数增长的递归栈。

FM 为每条超边缓存分区 0 的针脚数。移动顶点的增益是旧 cut-net 减去新 cut-net。源侧恰有一个针脚时贡献正边权，目标侧没有针脚时贡献负边权。单点超边的两项抵消。移动只在源分区保持非空、目标容量允许时执行。

成对交换只选择来自相反分区的两个未锁定顶点，先检查交换后的两个容量。交换增益在两者关联超边的并集上计算，共享超边只计一次。交换作为一个原子动作参与选择和前缀回滚。

每轮中移动过的顶点锁定。算法允许探索零增益或负增益动作，并记录迄今最小目标对应的动作前缀。轮末逆序撤销后缀，从原始图重新验证容量、非空性与目标，并检查缓存值一致。每轮返回目标不高于轮起点。

实现通过扫描选择候选。单点候选增益花费 O(deg(v))，交换候选花费 O(deg(a) + deg(b))，每轮还需 O(V + E + P) 初始化/复核工作。总工作由扫描、交换、移动、轮数及输入限额共同限制。该实现的扫描复杂度应与采用专用增益桶的经典 FM 实现区分评估。

验证器直接遍历原始图的针脚和最终赋值，O(V + E + P) 复算。它不使用 FM 的针脚计数、增益或移动历史。所有正常求解出口和分区文本导出均通过该验证路径。

测试包括独立枚举、每个单点/交换增益与全量目标差的对照、严格平衡交换、整数上界和后缀回滚。固定断连样本展示了局部搜索可能停滞的实际情况，结果记录保留在基准 JSON 中。
