在招聘专区看到某企业 超能饮料 谜题 故有此贴
我们知道，Spanning Tree（生成树）是连接一个无向连通图的每个节点的一棵树，而 Minimum Spanning Tree 则是一个图的所有生成树中边权值最小的。Minimum Spanning Tree 的算法有很多，比如常见的 Prim's Algorithm、Kruskal's Algorithm 等，还有 Borůvka's Algorithm 等。这个 Borůvka's Algorithm 也叫做 Sollin's Algorithm，Sollin 在二十世纪六十年代发现，但实际上捷克人 Otakar Borůvka 在1926年就发现了，之后又有不少人重新发现。
　　在学习最小生成树时，大家可能会有一个疑问，无向图有最小生成树，那么有向图呢？
有向图也有类似的树结构，叫做最小树形图，英文名称有很多，有 Minimum Arborescence、Minimum Branching 等多个名称，也有根据其特点称之为 Directed Minimum Spanning Tree（有向图的最小生成树）的。树形图是一棵有向树，它的根可以到达其他图的其他每个节点。最小树形图是一个图的所有树形图中边权值最小的。
　　那么如何求最小树形图呢？Prim's Algorithm、Kruskal's Algorithm 等用于求无向图最小生成树的算法是无法解决这个问题的。
　　解决该问题的第一个算法由朱永津和刘振宏在1965发表的，文章名为《关于最小树形图》。2年后，Jack Edmonds（就是那位发现了 Edmonds-Karp Algorithm 的数学家）也独立发现了同样的算法。这是一个由中国人的名字命名的算法！
　　先对根节点做一次 Depth First Search 即可判断根节点能否到达图中其他节点，如果不能则不存在最小树形图。

下面是求最小树形图的一个实现，时间复杂度为 Ο(|V|^3)
值得敬佩的是，朱永津是一位盲人。

#include <algorithm>
#include <cfloat>
#include <cstdio>
using namespace std;

const int N = 100;
bool visited[N];
int n;
double a[N][N]; //邻接矩阵

void DFS(int x)
{
    visited[x] = true;
    for (int i = 0; i < n; ++i)
        if (!visited[i] && a[x][i] < DBL_MAX-1) DFS(i);
}

double ZhuYongJin_LiuZhenHong()
{ //朱永津、刘振宏
    static bool flag[N];
    static int prev[N];
    double res = 0;
    fill_n(flag, n, false);
    for(;;)
    {
        int i;
        for (i = 1; i < n; ++i)
        {
            if (flag[i]) continue; //该点已被删除
            prev[i] = i;
            a[i][i] = INT_MAX; //删除自环
            for (int j = 0; j < n; ++j)
                if (!flag[j] && a[j][i] < a[prev[i]][i])
                    prev[i] = j;
        }
        for (i = 1; i < n; ++i)
        {
            if (flag[i]) continue;

            //寻找环
            int j = i;
            visited[0] = true;
            fill_n(visited+1, n-1, false);
            do visited[j] = true, j = prev[j];
            while (!visited[j]);

            if (!j) continue; //包含根节点
            i = j;
            res += a[prev[i]][i];
for (j = prev[i]; j != i; j = prev[j])
            {
                flag[j] = true; //删除环中除了 i 之外的所有节点
                res += a[prev[j]][j];
            }

            //w(j, i) 减去 w(prev(i), i)
            for (j = 0; j < n; ++j)
                if (!flag[j] && a[j][i] < DBL_MAX-1)
                    a[j][i] -= a[prev[i]][i];

            //修改和环关联的边的权值
            for (int k = 0; k < n; ++k)
                if (!flag[k])
                    for (j = prev[i]; j != i; j = prev[j])
                    {
                        if (a[j][k] < a[i][k]) a[i][k] = a[j][k];
                        if (a[k][j] < DBL_MAX-1 && a[k][j]-a[prev[j]][j] < a[k][i]) a[k][i] = a[k][j]-a[prev[j]][j];
                    }
            break;
        }
        if (i == n) //不再存在环
        {
            for (i = 1; i < n; ++i)
                if (!flag[i]) res += a[prev[i]][i];
            break;
        }
    }
    return res;
}

int main()
{
    int m, u, v;
    double w;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i < n; ++i)
            fill_n(a[i], n, DBL_MAX);
        for (; m; --m)
        {
            scanf("%d%d%lf", &u, &v, &w);
            a[v] = w;
        }
        fill_n(visited, n, false);
        DFS(0);
        for (int i = 1; i < n; ++i)
            if (!visited[i])
            {
                puts("最小树形图不存在");
                goto L1;
            }
        printf("%lf\n", ZhuYongJin_LiuZhenHong());
L1:;
    }
}
res←0

对于除了根节点外的每个节点 i，求出权值最小的入（1）边 (prev[i], i)。如果这些入边不构成环，那么入边的集合 E 即为所求。假设其中的一个环为 v0 <- v1 <- …… <- vk <- v0，那么如下更新原图：
w(v[0], u) = min{w(v[j], u)} (0 <= j <= k)
w(u, v[0]) = min{w(u, v[j]) - w(prev[j], j)} (0 <= j <= k)
并且 res 的值增加环中所有边的权值

重复以上操作，直到 E 中不存在环。此时 res 就是最小树形图的边权值之和。
w(u, v0) 之所以要修改为 min{w(u, v[j]) - w(prev[j], j)}，因为如果环外有个点 u 连向环中某一点 v[j]，那么加上之前算入 res 总和的 w(prev[j], j)，正好变成 w(u, v[j])。

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)