Day 115-Q3 | 大域最小カット（Stoer-Wagner法）

問題

$N$ 頂点 $M$ 辺の無向連結グラフがあり、各辺には重みがある。頂点集合を空でない2つの集合 $S, T$（$S \cup T = V$, $S \cap T = \emptyset$）に分割したとき、$S$ と $T$ をまたぐ辺の重みの合計をカットの重みと呼ぶ。全ての分割方法の中でカットの重みが最小となる値（大域最小カット）を求めよ。

入力形式

N M
u_1 v_1 c_1
u_2 v_2 c_2
...
u_M v_M c_M

同じ頂点対を結ぶ辺が複数与えられた場合は、その重みの総和を1本の辺として扱う。

制約

$2 \le N \le 300$

$N-1 \le M \le N(N-1)/2$

$1 \le c_i \le 10^9$

グラフは連結

入出力例

入力例1

出力例1

頂点1,2,3は重み3の辺で三角形をなし、頂点4は頂点3と重み1の辺でつながっているだけ。頂点4だけを孤立させるカットの重みが1で、これが最小。

概念図: Maximum Adjacency Search と cut-of-the-phase

ヒント（段階的開示）

ヒント1: 方向性

大域最小カットを求めるには、全ての頂点対 $(s,t)$ について $s$-$t$最小カット（$s$-$t$最大流と同じ値）を求めれば十分だが、それを $O(V^2)$ 回のmax-flowで計算するのは重すぎる。実は1つの頂点 $s$ を固定し、残り $N-1$ 頂点それぞれとの最小カットだけを考えれば大域最小カットが求まる、という事実を使うと計算回数を大きく減らせる。

ヒント2: アプローチ

Stoer-Wagner法は「Maximum Adjacency Search（最大隣接探索、MAS）」という貪欲な頂点追加順序を使う。集合 $A$ に、$A$への重み和が最大の頂点を1つずつ追加していく。この順序で最後に追加された2頂点を $s$（最後から2番目）, $t$（最後）とすると、「$t$ を他の頂点から切り離すカット」の重みがちょうど元のグラフの $s$-$t$最小カットに一致する（MAS定理）。これを求めたら $s$ と $t$ を1つの頂点にマージし、これを $N-1$ 回繰り返した中の最小値が大域最小カット。

ヒント3: 誘導（コード骨格）

# フェーズごとに:
#   wsum[] = 0 で初期化し、集合Aに頂点を1つずつ「wsum最大のもの」から追加
#   最後に追加された頂点を last、その直前を prev とする
#   cut_of_the_phase = wsum[last]  (lastが追加される直前の値)
#   best = min(best, cut_of_the_phase)
#   w[prev][*] += w[last][*]  として prev に last をマージし、last をグラフから除外

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx + 1]); idx += 2
    w = [[0] * N for _ in range(N)]
    for _ in range(M):
        u, v, c = int(data[idx]) - 1, int(data[idx + 1]) - 1, int(data[idx + 2])
        idx += 3
        w[u][v] += c
        w[v][u] += c

    exist = [True] * N
    best = float('inf')

    for phase in range(N - 1):
        in_a = [False] * N
        wsum = [0] * N
        prev = -1
        last = -1
        remaining = N - phase
        for _ in range(remaining):
            sel = -1
            for v in range(N):
                if exist[v] and not in_a[v]:
                    if sel == -1 or wsum[v] > wsum[sel]:
                        sel = v
            in_a[sel] = True
            prev, last = last, sel
            for v in range(N):
                if exist[v] and not in_a[v]:
                    wsum[v] += w[sel][v]

        cut_val = wsum[last]
        if cut_val < best:
            best = cut_val

        exist[last] = False
        for v in range(N):
            if exist[v]:
                w[prev][v] += w[last][v]
                w[v][prev] += w[v][last]

    print(best)

main()

計算量: 1フェーズあたりMaximum Adjacency Searchが $O(V^2)$、これを $N-1$ フェーズ行うので全体 $O(V^3)$。$N=300$で約$2.7\times10^7$回の基本演算。ランダムグラフに対し、全頂点対の最大流（Dinic法）で求めた最小カットの最小値と一致することを確認済み。

Step-by-Step 解説

1隣接行列で重みを管理する理由
頂点のマージ（縮約）を繰り返すため、w[u][v] += w[merged][v]のような更新がしやすい隣接行列表現が扱いやすい。

2Maximum Adjacency Search — wsum[]を使った貪欲な頂点追加
各ステップで「現在の集合 $A$ への合計重みが最大」の頂点を選んで $A$ に加える。1フェーズ $O(V^2)$。

3cut-of-the-phase = 最後に追加した頂点を孤立させる最小カット
MAS定理より、最後に追加された頂点 $t$（last）を他全頂点から切り離すカットの重みは、直前の $s$（prev）と $t$ の間の最小カットに一致する。

4最後の2頂点をマージして次のフェーズへ
$t$ を $s$ にマージする（$t$ の全辺を $s$ に付け替えて重みを加算し、$t$をexistから除外）。他の頂点対の最小カットの値は変化しないことが証明されている。

5$N-1$回のフェーズの中で最小値を取る
毎フェーズのcut_of_the_phaseの最小値が最終的な大域最小カットの値になる。

よくあるミス

ミス	原因	正しい書き方
有向グラフの最小カット問題と混同してしまう	最大流・最小カットの文脈から連想	Stoer-Wagner法は無向グラフ専用。$s$-$t$を固定せずに全頂点対の最小カットの最小値を1回の実行で求める
マージ後も`exist`配列を更新せず古い頂点を数えてしまう	マージ後の走査範囲をそのまま使う	`exist[last]=False`を必ず設定し、以降のループで`exist`を確認する
cut-of-the-phaseの値を`prev`の`wsum`から取ってしまう	「2番目に追加された頂点」の値と混同	cut-of-the-phaseは最後に追加された`last`の`wsum`の値
$N=2$などの最小ケースで境界条件を見落とす	ループ回数`N-1`が0や1になるケースの考慮不足	$N=2$なら`phase`ループは1回だけ回り、唯一の辺重みがそのまま答えになることを確認する

次のステップ

発展: 重みなし単純グラフに対する「辺連結度（edge connectivity）」を求める問題として解いてみる
発展: Gomory-Hu木（全頂点対の最小カットを木構造で表現する構造）と組み合わせ、任意の $s,t$ のカットを高速に答えられるようにする
発展: 最大流ベースの方法や乱択アルゴリズム（Karger-Stein法）と実行時間・実装量を比較する

自己評価

完全理解おおむね理解要復習

Day 115-Q3 — 無向グラフの大域最小カット（Stoer-Wagner法）

問題