説明

頂点 $r$ を根とする最小全域有向木を求めるアルゴリズム。頂点 $r$ から全ての頂点への経路が存在する木のうち最小コストのものを求める。

基本的には各頂点に入る辺のうち最小コストの辺を選ぶ。これらの辺からなるグラフが木ならそれが解。それ以外なら有向閉路が含まれているので閉路を縮約して適切に処理して, 閉路がなくなるまで再帰的に呼び出すことを繰り返す。

計算量

  • $O(E \log V)$

実装例

依存ライブラリ Skew-Heap

  • MinimumSpanningTreeArborescence($es$, $V$):= 頂点数 $V$ 重み付き辺集合 $es$ のグラフで初期化する。
  • build($start)$:= 頂点 $start$ を根とする最小全域有向木のコストを返す。全域有向木が存在しない時 $-1$ を返す。
template< typename T >
struct MinimumSpanningTreeArborescence
{
  using Pi = pair< T, int >;
  using Heap = SkewHeap< Pi, int >;
  using Node = typename Heap::Node;
  const Edges< T > &es;
  const int V;
  T INF;
 
  MinimumSpanningTreeArborescence(const Edges< T > &es, int V) :
      INF(numeric_limits< T >::max()), es(es), V(V) {}
 
  T build(int start)
  {
    auto g = [](const Pi &a, const T &b) { return Pi(a.first + b, a.second); };
    auto h = [](const T &a, const T &b) { return a + b; };
    Heap heap(g, h);
    vector< Node * > heaps(V, heap.makeheap());
    for(auto &e : es) heap.push(heaps[e.to], {e.cost, e.src});
    UnionFind uf(V);
    vector< int > used(V, -1);
    used[start] = start;
 
    T ret = 0;
    for(int s = 0; s < V; s++) {
      stack< int > path;
      for(int u = s; used[u] < 0;) {
        path.push(u);
        used[u] = s;
        if(heap.empty(heaps[u])) return -1;
        auto p = heap.top(heaps[u]);
        ret += p.first;
        heap.add(heaps[u], -p.first);
        heap.pop(heaps[u]);
        int v = uf.find(p.second);
        if(used[v] == s) {
          int w;
          Node *nextheap = heap.makeheap();
          do {
            w = path.top();
            path.pop();
            nextheap = heap.merge(nextheap, heaps[w]);
          } while(uf.unite(v, w));
          heaps[uf.find(v)] = nextheap;
          used[uf.find(v)] = -1;
        }
        u = uf.find(v);
      }
    }
    return ret;
  }
};

検証

AOJ GRL_2_A 最小全域有向木

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B"

#include "../../template/template.cpp"
#include "../template.cpp"

#include "../../structure/union-find.cpp"
#include "../../structure/skew-heap.cpp"

#include "../chu-liu-edmond.cpp"

int main() {
  int V, E, R;
  scanf("%d %d %d", &V, &E, &R);
  Edges< int > edges;
  for(int i = 0; i < E; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    edges.emplace_back(a, b, c);
  }
  printf("%d\n", MinimumSpanningTreeArborescence< int >(edges, V).build(R));
}