AIOJ

Definition

A minimum spanning tree on a directed graph (Directed Minimum Spanning Tree) is called a directed minimum spanning tree.

The commonly used algorithm is the Chu–Liu algorithm (also called Edmonds' algorithm), which solves the directed minimum spanning tree problem in $O(nm)$ time.

Process

For each vertex, choose the minimum-weight edge directed into it.
If there is no cycle, terminate; otherwise, contract the cycle and update the distances from the other vertices to the cycle.

Implementation

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's DMST algorithm

Tarjan proposed an algorithm that solves the directed minimum spanning tree problem in $O(m+n\log n)$ time.

The description and reference implementation here are based on Professor Uri Zwick's lecture notes; see the original text for more details.

Process

Tarjan's algorithm consists of two processes, contraction and expansion. We first introduce contraction.

We assume that the input graph is strongly connected. If it is not, add $O(n)$ edges to make it so, assigning these edges infinite weight.

We need a heap to store information such as the indices and weights of incoming edges and the total cost of each vertex. Since later steps merge heaps, we use a leftist tree and a disjoint-set union. At each step, choose an arbitrary vertex $v$ $v$ $v$ , ensuring that it is not the root and that its incoming edges are not already in the heap. Add the minimum incoming edge of to the heap. If this new edge makes the edges in the heap form a cycle, contract the vertices in that cycle; call the contracted vertices supervertices, and continue. If all vertices contract into one supervertex, the contraction process ends. It produces a contraction tree, on which we then perform expansion.

The edges in the heap always form a path $v_0\leftarrow v_1\leftarrow \dots\leftarrow v_k$ . Because the graph is strongly connected, this path exists; each $v_i$ may be an original single vertex or a contracted supervertex.

Initially, let $v_o=a$ , where $a$ is any vertex of the graph. Each time, choose a minimum incoming edge $v_k\leftarrow u$ . If $u$ is not one of $v_0,v_1,\dots,v_k$ , extend the path with $v_{k+1}=u$ . If $u$ is one of them, say $v_i$ , then a cycle $v_i\leftarrow\dots\leftarrow v_k\leftarrow v_i$ has been found; contract it into a supervertex $c$ .

Put all vertices and supervertices into a queue $P$ , initially choose any vertex $a$ , and perform the following steps while the queue is nonempty:

Choose the minimum incoming edge of $a$ , ensuring that it is not a self-loop, and find the vertex $b$ at its other endpoint. If $b$ has not been recorded, no cycle has formed; set $a\leftarrow b$ and continue searching for a cycle.
If $b$ has been recorded, a cycle has appeared. Increase the total number of vertices by one, renumber all vertices on the cycle, merge their heaps, and update the total weight of the vertices/supervertices. The weight update collects all incoming edges of the cycle's vertices and subtracts the weights of the cycle's incoming edges.

dmst1

In the figure, the strongly connected graph on the left becomes the contraction tree on the right. Here $a$ is the supervertex formed by contracting vertices 1 and 2; $b$ is the supervertex formed by contracting vertices 3, 4, and 5; and $A$ is formed by contracting the two supervertices $a$ and $b$ .

The expansion process is relatively simple. Starting from the originally required root $r$ , expand every cycle on the path from $r$ to the root of the contraction tree. Then start from the ancestor vertex $r$ of $f_r$ and expand the cycles on its path to the root until all vertices have been traversed.

Implementation

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

using ll = long long;
constexpr int MAXN = 102;
constexpr int 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];
  // Record every vertex and the vertices connected to it.
  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) {
    // Find the minimum incoming edge and its endpoint, ensuring that no cycle is formed.
    do {
      ed[a] = extract(Q[a]);
      a = id[ed[a]->u];
    } while (a == b && Q[a]);
    if (a == b) break;
    if (!mark[a]) continue;
    // Contract the discovered cycle, renumber its vertices, and update the total weight.
    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);
  }
  // Ensure strong connectivity
  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;
}

References

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

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

Directed minimum spanning tree

Definition

Process

Implementation

Tarjan's DMST algorithm

Process

Implementation

References