最小樹形圖

定義

有向圖上的最小生成樹（Directed Minimum Spanning Tree）稱為最小樹形圖。

常用的算法是朱劉算法（也稱 Edmonds 算法），可以在 \(O(nm)\) 時間內解決最小樹形圖問題。

過程

1. 對於每個點，選擇指向它的邊權最小的那條邊。
2. 如果沒有環，算法終止；否則進行縮環並更新其他點到環的距離。

實現

bool solve() {
  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;
}

Tarjan 的 DMST 算法

Tarjan 提出了一種能夠在 \(O(m+n\log n)\) 時間內解決最小樹形圖問題的算法。

這裏的算法描述以及參考代碼基於 Uri Zwick 教授的課堂講義，更多的細節可以參考原文。

過程

Tarjan 的算法分為 收縮 與 伸展 兩個過程。接下來先介紹 收縮 的過程。

我們需要假設輸入的圖是滿足強連通的，如果不滿足那麼就加入 \(O(n)\) 條邊使其滿足，並且這些邊的邊權是無窮大的。

我們需要一個堆存儲結點的入邊編號，入邊權值，結點總代價等相關信息，由於後續過程中會有堆的合併操作，這裏採用 左偏樹 與 並查集 實現。算法的每一步都選擇一個任意結點 \(v\)，需要保證 \(v\) 不是根節點，並且在堆中沒有它的入邊。再將 \(v\) 的最小入邊加入到堆中，如果新加入的這條邊使堆中的邊形成了環，那麼將構成環的那些結點收縮，我們不妨將這些已經收縮的結點命名為 超級結點，再繼續這個過程，如果所有的頂點都縮成了一個超級結點，那麼收縮過程就結束了。整個收縮過程結束後會得到一棵收縮樹，之後將對它進行伸展操作。

堆中的邊總是會形成一條路徑 \(v_0\leftarrow v_1\leftarrow \dots\leftarrow v_k\)，由於圖是強連通的，這個路徑必然存在，並且其中的 \(v_i\) 可能是最初的單一結點，也可能是壓縮後的超級結點。

最初有 \(v_o=a\)，其中 \(a\) 是圖中任意的一個結點，每一次選擇一條最小入邊 \(v_k\leftarrow u\)，如果 \(u\) 不是 \(v_0,v_1,\dots,v_k\) 中的一個結點，那麼就將結點擴展到 \(v_{k+1}=u\)。如果 \(u\) 是他們其中的一個結點 \(v_i\)，那麼就找到了一個關於 \(v_i\leftarrow\dots\leftarrow v_k\leftarrow v_i\) 的環，再將他們收縮為一個超級結點 \(c\)。

向隊列 \(P\) 中放入所有的結點或超級結點，並初始選擇任意一節點 \(a\)，只要隊列不為空，就進行以下步驟：

1. 選擇 \(a\) 的最小入邊，保證不存在自環，並找到另一頭的結點 \(b\)。如果結點 \(b\) 沒有被記錄過説明未形成環，令 \(a\leftarrow b\)，繼續當前操作尋找環。

2. 如果 \(b\) 被記錄過了，就説明出現了環。總結點數加一，並將環上的所有結點重新編號，對堆進行合併，以及結點/超級結點的總權值的更新。更新權值操作就是將環上所有結點的入邊都收集起來，並減去環上入邊的邊權。

以圖片為例，左邊的強連通圖在收縮後就形成了右邊的一棵收縮樹，其中 \(a\) 是結點 1 與結點 2 收縮後的超級結點，\(b\) 是結點 3，結點 4，結點 5 收縮後的超級結點，\(A\) 是兩個超級結點 \(a\) 與 \(b\) 收縮後形成的。

伸展過程是相對簡單的，以原先要求的根節點 \(r\) 為起始點，對 \(r\) 到收縮樹的根上的每一個環進行伸展。再以 \(r\) 的祖先結點 \(f_r\) 為起始點，將其到根的環展開，直到遍歷完所有的結點。

實現

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define maxn 102
#define INF 0x3f3f3f3f

struct UnionFind {
  int fa[maxn << 1];

  UnionFind() { memset(fa, 0, sizeof(fa)); }

  void clear(int n) { memset(fa + 1, 0, sizeof(int) * n); }

  int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }

  int operator[](int x) { return find(x); }
};

struct Edge {
  int u, v, w, w0;
};

struct Heap {
  Edge *e;
  int rk, constant;
  Heap *lch, *rch;

  Heap(Edge *_e) : e(_e), rk(1), constant(0), lch(NULL), rch(NULL) {}

  void push() {
    if (lch) lch->constant += constant;
    if (rch) rch->constant += constant;
    e->w += constant;
    constant = 0;
  }
};

Heap *merge(Heap *x, Heap *y) {
  if (!x) return y;
  if (!y) return x;
  if (x->e->w + x->constant > y->e->w + y->constant) swap(x, y);
  x->push();
  x->rch = merge(x->rch, y);
  if (!x->lch || x->lch->rk < x->rch->rk) swap(x->lch, x->rch);
  if (x->rch)
    x->rk = x->rch->rk + 1;
  else
    x->rk = 1;
  return x;
}

Edge *extract(Heap *&x) {
  Edge *r = x->e;
  x->push();
  x = merge(x->lch, x->rch);
  return r;
}

vector<Edge> in[maxn];
int n, m, fa[maxn << 1], nxt[maxn << 1];
Edge *ed[maxn << 1];
Heap *Q[maxn << 1];
UnionFind id;

void contract() {
  bool mark[maxn << 1];
  // 將圖上的每一個結點與其相連的那些結點進行記錄。
  for (int i = 1; i <= n; i++) {
    queue<Heap *> q;
    for (int j = 0; j < in[i].size(); j++) q.push(new Heap(&in[i][j]));
    while (q.size() > 1) {
      Heap *u = q.front();
      q.pop();
      Heap *v = q.front();
      q.pop();
      q.push(merge(u, v));
    }
    Q[i] = q.front();
  }
  mark[1] = true;
  for (int a = 1, b = 1, p; Q[a]; b = a, mark[b] = true) {
    // 尋找最小入邊以及其端點，保證無環。
    do {
      ed[a] = extract(Q[a]);
      a = id[ed[a]->u];
    } while (a == b && Q[a]);
    if (a == b) break;
    if (!mark[a]) continue;
    // 對發現的環進行收縮，以及環內的結點重新編號，總權值更新。
    for (a = b, n++; a != n; a = p) {
      id.fa[a] = fa[a] = n;
      if (Q[a]) Q[a]->constant -= ed[a]->w;
      Q[n] = merge(Q[n], Q[a]);
      p = id[ed[a]->u];
      nxt[p == n ? b : p] = a;
    }
  }
}

ll expand(int x, int r);

ll expand_iter(int x) {
  ll r = 0;
  for (int u = nxt[x]; u != x; u = nxt[u]) {
    if (ed[u]->w0 >= INF)
      return INF;
    else
      r += expand(ed[u]->v, u) + ed[u]->w0;
  }
  return r;
}

ll expand(int x, int t) {
  ll r = 0;
  for (; x != t; x = fa[x]) {
    r += expand_iter(x);
    if (r >= INF) return INF;
  }
  return r;
}

void link(int u, int v, int w) { in[v].push_back({u, v, w, w}); }

int main() {
  int rt;
  scanf("%d %d %d", &n, &m, &rt);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    link(u, v, w);
  }
  // 保證強連通
  for (int i = 1; i <= n; i++) link(i > 1 ? i - 1 : n, i, INF);
  contract();
  ll ans = expand(rt, n);
  if (ans >= INF)
    puts("-1");
  else
    printf("%lld\n", ans);
  return 0;
}

參考文獻

Uri Zwick. (2013),Directed Minimum Spanning Trees, Lecture notes on "Analysis of Algorithms"

https://riteme.site/blog/2018-6-18/mdst.html#_3

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用