以给定根 r 在有向图中选取每个点一条入边（根除外）使总权最小的最小树形图（Chu–Liu/Edmonds），不可达则判无解。
Description: Finds a minimum spanning tree/arborescence of a directed graph, given a root node. If no MST exists, returns -1. Time: O(E \log V)
-
定义与背景
- 目标：在有根有向图 G=(V,E) 中，选择恰好 |V|-1 条边，使除根 r 外每个点入度为 1，且从 r 可达所有点，总权最小。
- 术语：常称最小树形图（minimum arborescence）。与无向 MST 不同，必须基于“从根出发的入边选择+环收缩”处理方向性。
- 判无解：若存在从根 r 不可达的顶点，则不存在树形图，直接返回 -1。
-
典型适用场景
- 有向依赖/指派的“最小入边选择”，如有方向的安装/依赖链路成本优化。
- 在竞赛或工程中，当需要面向根的“覆盖所有节点”的最小代价有向树结构。
-
接口/数据结构（据实现习惯）
- Edge {a,b,w}：有向边 a→b，权 w。
- 斜堆（可并堆）：每个节点维护其“候选入边”最小堆，支持 merge/pop 以及对所有键的 lazy 增量（delta）。
- 并查集（DSU）：在收缩环时将多个点压成“超级点”，并维护代表元。
- 辅助结构：
- seen：访问标记，检测从某起点出发在“选最小入边”时形成的环。
- cycs：记录被收缩的环及其入边关系，用于后续解缩还原父指针。
- par：最终父指针（b 的父为其选中的入边起点 a）。
-
核心流程/要点（Chu–Liu/Edmonds）
- 可达性预检（可选）：从 r 做一次可达检查，不可达点直接判无解。
- 为每个 v≠r 准备“按入边权排序”的最小堆；r 的堆可置空或忽略。
- 主循环（逐个未访问的节点 s 为起点）：
- 重置 cur=s；累计 res=0；
- 重复：
- 从 cur 所在代表元的“入边堆”弹出最小边 e: a→cur，累加 res += e.w；
- 将“该代表元堆中的所有键”统一减去所选边权（lazy），表示把“选入边的权”归零，便于后续合并；
- 若 a 与 cur 属于同一连通代表（DSU 同组），则发现环：沿 seen 链回溯收集环中所有点 X；
- 将环内所有代表对应的堆 merge 为一个，并在 DSU 中合并为新代表 C；
- 记录环结构于 cycs，便于解缩重建；
- 将 cur 置为新代表 C，继续外层循环；
- 否则将 cur ← a 所在代表，继续寻找其最小入边；
- 当追溯至根 r 或遇到“无可用入边”则退出该条起点路径的处理。
- 解缩与重构
- 处理完成后，从 cycs 反向展开：每次用“被选入的零化边”还原环内父指针，并修正环中被替换的边（谁让出谁接入）。
- 最终得到每个 v≠r 的唯一父 par[v]，构成最小树形图。
-
复杂度与边界条件
- 时间复杂度：每条边最多入堆/弹出一次，堆操作 O(log V)，总体 O(E log V)。
- 不可达：若某代表元（非根）堆为空且仍未连接到 r，则无解（返回 -1）。
- 重边/自环：自环在入边选择中不会被选中；重边自然以权较小者胜出。
- 权值类型与上界：常用 64 位整型；若可能溢出需注意累加用 128 位中间量。
- 多根需求：可引入超级根 r* 指向所有真实根候选，边权为 0，然后求解并在结果中过滤掉 r* 出边。
-
变体/扩展与对比
- 与无向 MST（Kruskal/Prim）：无向 MST 基于连通性与边权全局排序；树形图需“每点入边最小化 + 环收缩”的有向结构。
- 与最短路（Dijkstra/Bellman–Ford 052-图论-贝尔曼福德）：最短路约束在路径；树形图是在全局“每点一入边”的集合约束下极小化总和。
- 回滚并查集 016-数据结构-回滚并查集：若需在解缩或尝试不同根/边集时回溯，可配合回滚 DSU 降低实现复杂度。
- 全局最小割 064-图论-全局最小割：最小割/流刻画连通性分割；树形图是“选择入边”的构造性问题，模型不同。
-
正确性要点与不变式
- 最小入边不变式：对当前代表元 X，选其最小入边并将该边权“归零”后，后续在该代表的相对比较中不再重复计此边权。
- 环收缩不变式：当形成环时，将其视作一个“超级点”并合并其入边堆；解缩时保证环内仅替换一条边，从而维持每点入度 1。
- 终止性：每次收缩至少减少一个代表元；有限步后终止并可成功还原父关系或判无解。
-
与相邻技术的对比与取舍建议
- 若只需无向 MST，应使用 Prim/Kruskal；若方向重要且需从根覆盖所有点，则本算法是标准解。
- 当图稀疏、边权正负混合亦可处理（不涉及路径松弛），但务必保证从根可达性。
- 若进一步需要“成本+容量”等多维权衡，应改造为更通用的优化模型（超出本节点范围）。