最小树形图

概念

最小树形图（Directed Minimum Spanning Tree, DMST）：给定一张有向带权图 $G = (V, E)$ 和根节点 $r$ ，树形图是一棵以 $r$ 为根的有向生成树——它包含所有节点，除根节点外每个节点恰好有一条入边，且从根 $r$ 出发能到达所有节点。所有树形图中边权和最小的称为最小树形图。

与无向图的最小生成树不同，Kruskal、Prim 都依赖无向边的对称性；而有向图中"每个点恰好选一条入边"还会受到方向顺序的约束，因此需要专门的算法。最常用的是朱刘算法（Zhu-Liu 算法，也称 Edmonds 算法），时间复杂度 $O (n m)$ 。

朱刘算法

算法流程

算法的核心思想是"贪心选入边 + 缩环再迭代"：

选择最小入边：对每个非根节点 $v$ ，在所有指向 $v$ 的边中选择权值最小的，记最小权值为 $i n [v]$ 、边的起点为 $p r e [v]$ 。若某个非根节点没有任何入边，则不存在最小树形图，直接判定无解。
判断是否有环：若选出的 $n - 1$ 条边不构成环，这些边就是一棵树形图，累加所有 $i n [v]$ 即为答案。
缩环：若存在环，把环上的所有点缩成一个"超级点"。环上边的权值已经计入答案；对于原来指向环内点 $v$ 的边 $(u, v)$ ，将其权值改为 $w (u, v) - i n [v]$ ，然后在新图上重复上述过程。

为什么是 $w (u, v) - i n [v]$

环被缩成超级点后，环内部已经"确定"选入了边 $i n [v]$ 。将来如果要用一条新边 $(u, v)$ 替换掉环上进入 $v$ 的那条边，整体边权和的变化量正好是 $w (u, v) - i n [v]$ 。把这个差值作为新边的权值，就能保证"缩点后的最优解 + 环的权值和 = 原图的最优解"，这是算法正确性的关键。

正确性

无解判定是必要的：树形图中每个非根节点必须恰好有一条入边，若某点连入边都没有，必然无解。
缩环是保最优的：任意一棵最小树形图都可以由"环缩点后的一棵更小树形图 + 环上边集"构造出来，两者权值一一对应，因此缩环后求出的最优解与原问题一致。
算法必然终止：每轮至少缩掉一个环，节点数严格减少，最多 $O (n)$ 轮。

复杂度

每轮需要扫描所有边找最小入边并更新边权，一轮 $O (m)$ ，最多 $O (n)$ 轮，总时间复杂度 $O (n m)$ ，空间 $O (n + m)$ 。

扩展：OI Wiki 还介绍了 Tarjan 提出的 $O (m + n \log n)$ 算法，用左偏树（可并堆）与并查集维护每个点的入边堆，实现较为复杂；竞赛中朱刘算法更常用。

洛谷 P4716 【模板】最小树形图

给定包含 $n$ 个节点、 $m$ 条有向边的图，求以节点 $r$ 为根的最小树形图的边权之和；若不存在，输出 $- 1$ 。其中 $n \leq 100$ ， $m \leq 10^{4}$ ， $w \leq 10^{6}$ 。

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 10010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int a, b, w;
} e[M];

int n, m, r;
int in[N], pre[N], id[N], vis[N];

int zhu_liu() {
    int ans = 0;

    while (true) {
        // 1. 为每个非根点选择最小入边
        for (int i = 1; i <= n; i++) in[i] = INF;

        for (int i = 0; i < m; i++) {
            int a = e[i].a, b = e[i].b, w = e[i].w;
            if (a != b && w < in[b]) {
                in[b] = w;
                pre[b] = a;
            }
        }

        // 2. 存在无入边的点则无解
        for (int i = 1; i <= n; i++) {
            if (i != r && in[i] == INF) return -1;
        }

        // 3. 沿着 pre 找环
        memset(id, 0, sizeof id);
        memset(vis, 0, sizeof vis);
        in[r] = 0;

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            ans += in[i];

            int cur = i;
            while (vis[cur] != i && id[cur] == 0 && cur != r) {
                vis[cur] = i;
                cur = pre[cur];
            }

            if (cur != r && id[cur] == 0) {
                id[cur] = ++cnt;
                for (int j = pre[cur]; j != cur; j = pre[j]) {
                    id[j] = cnt;
                }
            }
        }

        if (cnt == 0) break;  // 没有环，当前选出的边就是答案

        // 4. 缩点并更新边权，继续迭代
        for (int i = 1; i <= n; i++) {
            if (id[i] == 0) id[i] = ++cnt;
        }

        for (int i = 0; i < m; i++) {
            int a = e[i].a, b = e[i].b;
            e[i].a = id[a];
            e[i].b = id[b];
            if (e[i].a != e[i].b) e[i].w -= in[b];
        }

        n = cnt;
        r = id[r];
    }

    return ans;
}

int main() {
    cin >> n >> m >> r;

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }

    cout << zhu_liu() << endl;

    return 0;
}

POJ 3164 Command Network

平面上有 $N$ 个节点， $M$ 条可建设的单向线路，线路权值为两端点的欧氏距离。总部位于节点 $1$ ，求从总部出发能覆盖所有节点的最小线路总长度，保留两位小数；若无法建成，输出 poor snoopy。 $N \leq 100$ ， $M \leq 10^{4}$ ，多组数据。这是最小树形图的经典浮点版本，边权改为两点距离即可。

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 10010;
const double INF = 1e18;

struct Edge {
    int a, b;
    double w;
} e[M];

double x[N], y[N];
int n, m;
double in[N];
int pre[N], id[N], vis[N];

double get_dist(int i, int j) {
    double dx = x[i] - x[j], dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

double zhu_liu(int root) {
    double ans = 0;

    while (true) {
        for (int i = 1; i <= n; i++) in[i] = INF;

        for (int i = 0; i < m; i++) {
            int a = e[i].a, b = e[i].b;
            if (a != b && e[i].w < in[b]) {
                in[b] = e[i].w;
                pre[b] = a;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (i != root && in[i] > INF / 2) return -1;
        }

        memset(id, 0, sizeof id);
        memset(vis, 0, sizeof vis);
        in[root] = 0;

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            ans += in[i];

            int cur = i;
            while (vis[cur] != i && id[cur] == 0 && cur != root) {
                vis[cur] = i;
                cur = pre[cur];
            }

            if (cur != root && id[cur] == 0) {
                id[cur] = ++cnt;
                for (int j = pre[cur]; j != cur; j = pre[j]) {
                    id[j] = cnt;
                }
            }
        }

        if (cnt == 0) break;

        for (int i = 1; i <= n; i++) {
            if (id[i] == 0) id[i] = ++cnt;
        }

        for (int i = 0; i < m; i++) {
            int a = e[i].a, b = e[i].b;
            e[i].a = id[a];
            e[i].b = id[b];
            if (e[i].a != e[i].b) e[i].w -= in[b];
        }

        n = cnt;
        root = id[root];
    }

    return ans;
}

int main() {
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> y[i];
        }

        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            e[i] = {a, b, get_dist(a, b)};
        }

        double ans = zhu_liu(1);
        if (ans < 0) puts("poor snoopy");
        else printf("%.2f\n", ans);
    }

    return 0;
}

参考资料

OI Wiki：最小树形图

最小树形图 ​

概念 ​

朱刘算法 ​

算法流程 ​

为什么是 w(u,v)−in[v] ​

正确性 ​

复杂度 ​

洛谷 P4716 【模板】最小树形图 ​

POJ 3164 Command Network ​

参考资料 ​