朱刘算法学习笔记

一句话概括：

朱刘算法就是最小生成树算法在有向图中的应用。

树形图：

• 无环

• 除了根以外，每个点的入度为1

最小树形图：一个有向图，存在从某个点开始的到达所有的的一个最小生成树。

核心思想：贪心

时间复杂度：\(O(nm)\)

算法步骤：

1. 对于每个点（除根以外），选择它入边中边权最小的那条边。

2. 如果没有环，算法终止；否则进行缩环并更新其他点到环的距离。

3. 将所有环缩点，得到新图\(h'\)

code

bool zhu_liu() {
  ans = 0;
  int u, v, root = 0;
  for (;;) {
    f(i, 0, n) in[i] = 1e100;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      if (u != v && e[i].w < in[v]) {
        in[v] = e[i].w;
        pre[v] = u;
      }
    }
    f(i, 0, m) if (i != root && in[i] > 1e50) return 0;
    int tn = 0;
    memset(id, -1, sizeof id);
    memset(vis, -1, sizeof vis);
    in[root] = 0;
    f(i, 0, n) {
      ans += in[i];
      v = i;
      while (vis[v] != i && id[v] == -1 && v != root) {
        vis[v] = i;
        v = pre[v];
      }
      if (v != root && id[v] == -1) {
        for (int u = pre[v]; u != v; u = pre[u]) id[u] = tn;
        id[v] = tn++;
      }
    }
    if (tn == 0) break;
    f(i, 0, n) if (id[i] == -1) id[i] = tn++;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      e[i].s = id[u];
      e[i].t = id[v];
      if (e[i].s != e[i].t) e[i].w -= in[v];
    }
    n = tn;
    root = id[root];
  }
  return ans;
}