对于个点条边的边带权有向图（无自环，允许重边），并给定一个结点作为根结点，朱-刘算法（Chu–Liu/Edmonds’ algorithm）可在的时间内求出以为根的最小权外向生成树，即最小树形图，或判断无解。

Tarjan 算法是对其的进一步优化。本文仅介绍朱-刘算法有关内容。

朱-刘算法

朱-刘算法的基本思想是将有向图的环缩点，转化为有向无环图（DAG）的最小树形图问题。

对于每个非的结点，设表示权值最小的的入边（到达的边）。若不存在，直接判定为无解。

如果这些边构造的子图，即，无环，那么容易证明是最小树形图的方案之一。

证明

最小权是显然的。

考虑从任意非的结点开始沿着反向走。由于无环，那么最后一定会停在上。因此可以沿着中的边到达任意结点。因此这构成了一棵外向生成树。

如果有环，那么可以证明：存在一种最小树形图的方案，使得环上只有一条边没有被选，其他边都被选。

不妨设这个环上的点的点集为，那么我们可以把这个环缩点成。且我们先把环上的边都选了。

且对于（），我们将变成，含义为：如果我选择了这条边，我就要放弃这条边。

由于根结点必然不在环中（因为我们只对非的结点求），因此必然有恰好一条入边被选，这样环上的某一条边就会被放弃，破环为链，这就保证了缩点算法得到的结果一定是树形图。

我们不停地按照上述过程缩点，直到没有环。这样就转化为了 DAG 的最小树形图问题。

时间复杂度。

代码实现

在实现的时候我们可以类似并查集一样记录每个点被缩点到了哪个点里。如果一条边的两个端点被缩到同一个点里，那么这条边相当于被删除了。

记录方案的时候只需要记每条边被选后需要放弃的边的集合，再记录每条边被选的时间，然后按照时间从后往前更新被选的状态即可（因为有的边被选了可能会在之后的缩点过程中被放弃）。

#include<bits/stdc++.h>
#define FOR(a, b, c) for(int a = (int)(b); a <= (int)(c); a++)
#define ROF(a, b, c) for(int a = (int)(b); a >= (int)(c); a--)
using namespace std;

struct Edge {
  int u, v, w, ow;
  Edge(int _u, int _v, int _w) { u = _u, v = _v, w = ow = _w; }
  void reset () { w = ow; }
};

/**
 * Chu-Liu/Edmonds' algorithm
 * 计算有向图（允许重边、不允许自环）给定根的最小权外向生成树（最小树形图）
 * vector<Edge> buildFrom(n, r, ve): n 个点，边集是 ve，根是 r 的最小权外向生成树
 *   若无解则返回一个空的 vector
 *   要求 ve 非空
 */
template<const int N, const int M>
struct DirectedMST {
  int nd[N], tnd[N], fa[N], pre[N], In[N], Time[M], totTime, onCir[N], totCir;
  vector<int> toggle[M];

  int get(int u) { return fa[u] == u ? u : fa[u] = get(fa[u]); }
  int getNode(int u) { return nd[u] == u ? u : nd[u] = getNode(nd[u]); }

  bool work(const int n, const int root, vector<Edge> & ve) {
    bool flag = false;
    fill(In, In + n + 1, -1);
    fill(onCir, onCir + n + 1, 0);
    totCir = 0;

    for(unsigned i = 0; i < ve.size(); i++){ // calculate e_min(v)
      int u = getNode(ve[i].u), v = getNode(ve[i].v);
      if(u == v) continue;
      if(In[v] == -1 || ve[In[v]].w > ve[i].w) In[v] = i;
    }

    FOR(i, 1, n) fa[i] = i;

    FOR(i, 1, n) if(i != root && getNode(i) == i) {
      if(In[i] == -1) return false;
      Edge e = ve[In[i]];
      int u = getNode(e.u), v = getNode(e.v);
      if(u == v) continue;
      if(get(u) == get(v)) { // find a circle
        ++totCir;
        for(int z = u; z != -1; z = z == v ? -1 : getNode(ve[In[z]].u)) 
          onCir[z] = totCir, tnd[z] = v, Time[In[z]] = ++totTime; // assert(z);
        flag = true;
      } else {
        fa[get(u)] = get(v);
      }
    }  

    for(unsigned i = 0; i < ve.size(); i++){ // shrink
      auto & e = ve[i];
      int u = getNode(e.u), v = getNode(e.v);
      if(u == v) continue;
      if(onCir[v] && onCir[v] == onCir[u]) continue;
      if(onCir[v]) toggle[i].push_back(In[v]), e.w -= ve[In[v]].w;
    }

    FOR(i, 1, n) if(onCir[i]) nd[i] = tnd[i]; // assert(getNode(i) == i);

    return flag;
  }
  vector<Edge> buildFrom(int n, int root, vector<Edge> ve) {
    assert(!ve.empty());
    vector<Edge> vt;
    FOR(i, 1, n) nd[i] = i;
    fill(Time, Time + ve.size() + 1, 0);
    totTime = 0;

    while(work(n, root, ve));

    FOR(i, 1, n) if(getNode(i) == i && i != root) {
      if(In[i] == -1) return vt; // empty
      Time[In[i]] = ++totTime;
    }
    vector<int> SortByTime(totTime + 1, -1);
    for(unsigned i = 0; i < ve.size(); i ++)
      if(Time[i]) SortByTime[Time[i]] = i;

    ROF(i, totTime, 1) {
      int x = SortByTime[i];
      if(Time[x]) for(int y: toggle[x]) Time[y] = 0;
    }

    for(unsigned i = 0; i < ve.size(); i ++) {
      ve[i].reset(); // set w to ow (namely original weight)
      if(Time[i]) vt.push_back(ve[i]);
    }
    assert(vt.size() == n - 1);
    return vt;
  }
};

「例题」Dictionary1

有个字符串，要求构造一棵字典树使得每个字符串都在字典树中以「从祖先到儿子的路径」的形式出现过（不一定是从根结点出发）。

最小化字典树的结点数，并输出构造的方案。

。

容易发现我们可以维护一棵字典树，每次将一个字符串的前缀与中的一个「从祖先到儿子的路径」构成的字符串“贴”到一起，这样可以合并个字符串来得到一棵字典树。

因此我们预处理表示第个串的子串与第个串的前缀匹配的最长长度。那么构造一个完全有向图，使得的权值为，则原问题就转化为：枚举根结点，求出这个图的最大树形图。

在求出了最大树形图的方案后，就容易构造字典树的方案了。

时间复杂度。

当然，由于本题的字符串长度较小，可以直接按照题解的算法建字典图求最小树形图。

代码

1. ACM ICPC 2013–2014, Northeastern European Regional Contest (NEERC) Prob. D ↩