Gomory-Hu 木

説明

連結な無向重みつきグラフ G = (V, E) に対し，重みつき木 T が Gomory-Hu 木，またはカット木であるとは，次の二条件を満たすことをいう．

• T の点集合は G の点集合と等しい（辺は制限しない）．
• mincut(u, v; G) = mincut(u, v; T)．

任意のグラフに対し，Gomory-Hu 木が存在することが証明できる．

たくさんの点対に対して最小カットを計算しなければならない場合，あらかじめ Gomory-Hu 木を計算しておけば，G の最小カットのかわりに T の最小カットを求めればよくなるため，効率的に計算できる（木の最小カットは経路上の最小重みなので簡単に求まる．

Gomory-Hu 木を計算するアルゴリズムは，まず Gomory と Hu によって，頂点を圧縮しながら最大流を O(V) 回計算するものが提案された．その後 Gusfield によってアルゴリズムが整理され，陽に頂点の圧縮を行なう必要の無いアルゴリズムが提案された．以下の実装は Gusfield の提案したものによる．

計算量

O(V MAXFLOW)．

使い方

Graph cutTree(const Graph & g)

無向（すべての辺に逆辺がある）グラフ g の Gomory-Hu 木を計算する．内部で隣接行列にしているが，速度に問題がある場合は予め隣接行列にして渡すこと．

戻り値として Gomory-Hu 木を返す．

Weight maximumFlow(const Graph &T, int s, int t)

s-t 最大流を Gomory-Hu 木 T を用いて計算する．単なる深さ優先探索．

ソースコード

#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
Graph cutTree(const Graph &g) {
  int n = g.size();
  Matrix capacity(n, Array(n)), flow(n, Array(n));
  REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;

  vector<int> p(n), prev;
  vector<Weight> w(n);
  for (int s = 1; s < n; ++s) {
    int t = p[s]; // max-flow(s, t)
    REP(i,n) REP(j,n) flow[i][j] = 0;
    Weight total = 0;
    while (1) {
      queue<int> Q; Q.push(s);
      prev.assign(n, -1); prev[s] = s;
      while (!Q.empty() && prev[t] < 0) {
        int u = Q.front(); Q.pop();
        FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
          prev[e->dst] = u;
          Q.push(e->dst);
        }
      }
      if (prev[t] < 0) goto esc;
      Weight inc = INF;
      for (int j = t; prev[j] != j; j = prev[j])
        inc = min(inc, RESIDUE(prev[j], j));
      for (int j = t; prev[j] != j; j = prev[j])
        flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
      total += inc;
    }
esc:w[s] = total; // make tree
    REP(u, n) if (u != s && prev[u] != -1 && p[u] == t)
      p[u] = s;
    if (prev[p[t]] != -1)
      p[s] = p[t], p[t] = s, w[s] = w[t], w[t] = total;
  }
  Graph T(n); // (s, p[s]) is a tree edge of weight w[s]
  REP(s, n) if (s != p[s]) {
    T[  s ].push_back( Edge(s, p[s], w[s]) );
    T[p[s]].push_back( Edge(p[s], s, w[s]) );
  }
  return T;
}

// Gomory-Hu tree を用いた最大流 O(n)
Weight maximumFlow(const Graph &T, int u, int t, int p = -1, Weight w = INF) {
  if (u == t) return w;
  Weight d = INF;
  FOR(e, T[u]) if (e->dst != p)
    d = min(d, maximumFlow(T, e->dst, t, u, min(w, e->weight)));
  return d;
}

Verified