Day 085-Q3 — Gomory-Hu Tree（全点対最小カット木・$N-1$ 回最大流）

問題

$N$ 頂点 $M$ 辺の連結な無向重み付きグラフが与えられる。$Q$ 個のクエリ $(s_i, t_i)$ に対し、$s_i$-$t_i$ 間の最小カット（＝最大流）の値を答えよ。

全点対の最小カットは Gomory-Hu Tree（等価フロー木）で表現できる。この木を $N-1$ 回の最大流計算で構築し、各クエリは木上パスの最小辺重みで答えられる。

入出力例

4 5
0 1 3
0 2 2
1 2 2
1 3 2
2 3 3
2
0 3
1 2

5
4

概念図: 元グラフ → Gomory-Hu 木 → パス最小辺クエリ

$\text{mincut}(u,v) = $ 木上 $u$-$v$ パス上の最小辺重み。全 $\binom{N}{2}$ 対を $N-1$ 個の木辺で表現する。

ヒント

parent = [0]*N; weight = [0]*N
for i in range(1, N):
    p = parent[i]
    f = max_flow(i, p)          # Dinic を毎回リセット
    S = reachable_from_i_in_residual()
    weight[i] = f
    for j in range(i+1, N):
        if j in S and parent[j] == p:
            parent[j] = i

模範解答

import sys
from collections import deque
input = sys.stdin.readline

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to = []; self.cap = []; self.rev = []
        self.g = [[] for _ in range(n)]
    def add_edge(self, u, v, c):
        self.g[u].append(len(self.to)); self.to.append(v); self.cap.append(c); self.rev.append(len(self.to))
        self.g[v].append(len(self.to)); self.to.append(u); self.cap.append(c); self.rev.append(len(self.to)-2)
    def bfs(self, s, t):
        self.level = [-1]*self.n; self.level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for e in self.g[v]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[v]+1; q.append(self.to[e])
        return self.level[t] >= 0
    def dfs(self, v, t, f):
        if v == t: return f
        while self.it[v] < len(self.g[v]):
            e = self.g[v][self.it[v]]; u = self.to[e]
            if self.cap[e] > 0 and self.level[u] == self.level[v]+1:
                d = self.dfs(u, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d; self.cap[self.rev[e]] += d; return d
            self.it[v] += 1
        return 0
    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0: break
                flow += f
        return flow
    def side(self, s):
        seen = [False]*self.n; seen[s] = True; q = deque([s])
        while q:
            v = q.popleft()
            for e in self.g[v]:
                if self.cap[e] > 0 and not seen[self.to[e]]:
                    seen[self.to[e]] = True; q.append(self.to[e])
        return seen

def solve():
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    def build():
        d = Dinic(N)
        for u, v, w in edges: d.add_edge(u, v, w)
        return d

    parent = [0]*N; weight = [0]*N
    for i in range(1, N):
        p = parent[i]
        d = build()
        f = d.max_flow(i, p)
        seen = d.side(i)
        weight[i] = f
        for j in range(i+1, N):
            if seen[j] and parent[j] == p:
                parent[j] = i

    tree = [[] for _ in range(N)]
    for i in range(1, N):
        tree[i].append((parent[i], weight[i]))
        tree[parent[i]].append((i, weight[i]))

    INF = float('inf')
    Q = int(input()); out = []
    for _ in range(Q):
        s, t = map(int, input().split())
        best = [-1]*N; best[s] = INF; q = deque([s])
        while q:
            v = q.popleft()
            for u, w in tree[v]:
                if best[u] == -1:
                    best[u] = min(best[v], w); q.append(u)
        out.append(best[t])
    print('\n'.join(map(str, out)))

solve()

計算量: 構築 $O(N \cdot \text{MaxFlow})$、各クエリ $O(N)$。

Step-by-Step 解説

Step 1: Gomory-Hu の定理

無向グラフの全点対最小カットは高々 $N-1$ 個の異なる値を取り、それらを辺重みとする木で表現できる。木上 $u$-$v$ パスの最小辺 = $\text{mincut}(u,v)$。

Step 2: Gusfield の簡易構築

本来の Gomory-Hu は縮約を伴い難しい。Gusfield 版は縮約なしで parent 配列の逐次更新だけで正しい等価フロー木の辺重みを得られる。

Step 3: min-cut の側集合

$i$-$p$ 最大流の残余で $i$ から到達可能な集合 $S$ が「$i$ 側」。$j>i$ で親が同じ $p$ かつ $j\in S$ の頂点を $i$ に付け替える。

Step 4: クエリ応答

よくあるミス

次のステップ

• 発展問題: 全点対最小カットの最大値（木の最小辺）を $N-1$ 回流で求める
• 発展問題: 動的にグラフ辺重みが変わる場合の等価フロー木再構築

自己評価