有向图最小生成树 (朱-刘算法 / 最小树形图)¶

在有向加权图 \(G\) 中，指定一个根节点 \(R\)。求一棵以 \(R\) 为根的有向生成树（从 \(R\) 出发可到达所有其他顶点），使得树上所有边的权值之和最小。该问题被称为最小树形图 (Optimum Branching / Arborescence)。

朱-刘算法 (Chu-Liu/Edmonds 算法) 是求解有向图最小生成树的经典算法，其思想基于贪心选择最小入边 + 环收缩 (Cycle Contraction)。

算法核心步骤¶

贪心寻找最小入边：
对于除根节点 \(R\) 之外的每个顶点 \(u\)，寻找一条指向它的边权最小的有向入边 \(e = (v, u)\)，记其权值为 \(in\_cost[u]\)。
若存在某个顶点没有入边，说明该图无法形成树形图，无解。
环路判定：
检查所有被选中的最小入边构成的子图是否包含环。
若不存在环：说明选中的边恰好构成了一棵合法的有向生成树，累加所有 \(in\_cost\) 即为最小权值和，算法结束。
若存在环：将每个环收缩为一个虚拟的“超节点”（缩点），对于外部节点指向环内节点 \(v\) 的每条边，将其边权更新为 \(w - in\_cost[v]\)（因为引入该外来入边将破除环内指向 \(v\) 的入边）。
递归迭代：在新收缩的图上重复上述步骤，直到图中不再包含任何环。

时间复杂度：\(\mathcal{O}(V \cdot E)\)。

完整模版实现¶

#include <vector>
#include <algorithm>

constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct DirectedEdge {
    int u, v;
    long long w;
};

// n: 顶点数, root: 指定根节点 (0-indexed)
// 返回最小树形图的总权值，若无法构成则返回 -1
long long chu_liu(int n, int root, std::vector<DirectedEdge> edges) {
    long long ans = 0;

    while (true) {
        // 1. 为每个非根节点寻找最小入边
        std::vector<long long> in_cost(n, INF);
        std::vector<int> pre(n, -1);

        for (const auto &e : edges) {
            if (e.u != e.v && e.w < in_cost[e.v]) {
                in_cost[e.v] = e.w;
                pre[e.v] = e.u;
            }
        }

        // 检查是否存在不可达孤立点
        for (int i = 0; i < n; ++i) {
            if (i == root) continue;
            if (in_cost[i] == INF) return -1; // 存在无入边的节点，无解
        }

        // 2. 环路检测与缩点
        int cycle_cnt = 0;
        std::vector<int> id(n, -1);
        std::vector<int> vis(n, -1);
        in_cost[root] = 0;

        for (int i = 0; i < n; ++i) {
            ans += in_cost[i];
            int v = i;
            // 沿 pre 前驱指针追踪环
            while (v != root && id[v] == -1 && vis[v] != i) {
                vis[v] = i;
                v = pre[v];
            }
            // 发现环，为环内所有节点分配相同的新编号
            if (v != root && id[v] == -1) {
                for (int u = pre[v]; u != v; u = pre[u]) {
                    id[u] = cycle_cnt;
                }
                id[v] = cycle_cnt++;
            }
        }

        // 若没有环，算法终止，当前 ans 即为最优解
        if (cycle_cnt == 0) break;

        // 为未在环中的非环节点赋予独立新编号
        for (int i = 0; i < n; ++i) {
            if (id[i] == -1) {
                id[i] = cycle_cnt++;
            }
        }

        // 3. 构造缩点后的新边权
        std::vector<DirectedEdge> next_edges;
        for (const auto &e : edges) {
            int u = id[e.u];
            int v = id[e.v];
            if (u != v) {
                // 边权减去进入环的原有内边代价
                next_edges.push_back({u, v, e.w - in_cost[e.v]});
            }
        }

        edges = std::move(next_edges);
        n = cycle_cnt;
        root = id[root];
    }

    return ans;
}