Day 095-Q1 — Stoer-Wagner法（大域最小カット）

2026-07-17 赤色 Master / Phase 8+ ★★★★★★★★★ 大域最小カット・Maximum Adjacency Search

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフが与えられる。始点・終点を指定しない「大域最小カット（global minimum cut）」を求めよ。

大域最小カットとは、頂点集合を空でない2つの部分集合 $S, V\setminus S$ に分割したとき、$S$ と $V\setminus S$ の間を跨ぐ辺の重みの総和を最小化する値である。あらゆる分割について最小値を求める必要がある（$s$-$t$ 最小カットを $\binom{N}{2}$ 通り全て解くと $O(N)$ 倍の計算が必要になるため、それより高速なアルゴリズムが要求される）。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M

多重辺が存在する場合は重みを合算して1本の辺として扱う。

制約

$2 \le N \le 300$
$1 \le M \le \frac{N(N-1)}{2}$
$1 \le w_i \le 10^9$
グラフは連結

入出力例

入力例1

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

出力例1

4

頂点1だけを分離するカット（3+1=4）と頂点4だけを分離するカット（1+3=4）がともに最小で、大域最小カットは4。

概念図

大域最小カット: 頂点1を孤立させる分割（重み4） 1 2 3 4 w=3 (跨ぐ) w=1 (跨ぐ) w=3 w=1 w=3 破線（オレンジ）が S={1} と V\S={2,3,4} を跨ぐカット辺。合計重み = 3+1 = 4 緑の辺は S 内・V\S 内の辺でカットに含まれない

ヒント（段階的開示）

ヒント1: 方向性
固定した $s,t$ に対する最小カットを $\binom{N}{2}$ 通り全部計算すれば答えは求まるが、それでは計算量が大きすぎる。「$s,t$ を固定せずに、1回の探索で必ずどこかの $s$-$t$ 最小カットの値を1つ確定させる」手続きを $N-1$ 回繰り返す方法を考えよ。
ヒント2: アプローチ
Maximum Adjacency Search（最大近接順序）を使う。集合 $A$ を1頂点から始め、「$A$ に隣接する重みの総和が最大の頂点」を1つずつ加えていく。最後に加わった頂点を $t$、その直前を $s$ とすると、「$t$ だけを孤立させるカットの重み」が $s$-$t$ 最小カットの値と一致する（Stoer-Wagnerの定理）。この値を記録後、$s,t$ をマージして頂点が1つになるまで繰り返す。
ヒント3: 誘導（コード骨格） 
def phase(v, graph):
    m = len(v)
    w = [0] * m
    added = [False] * m
    prev, last = -1, -1
    for i in range(m):
        sel = max((j for j in range(m) if not added[j]), key=lambda j: w[j])
        if i == m - 1:
            return sel, prev, w[sel]   # (t, s, cut-of-the-phase)
        added[sel] = True
        prev, last = last, sel
        for j in range(m):
            if not added[j]:
                w[j] += graph[v[sel]][v[j]]

各フェーズで得た (t, s, cut値) を使い、graph[v[s]] に graph[v[t]] を加算してマージし、v から t を除去する。

模範解答 (Python)

import sys


def stoer_wagner(n, graph):
    v = list(range(n))
    best_cut = float('inf')
    while len(v) > 1:
        m = len(v)
        w = [0] * m
        added = [False] * m
        prev = -1
        last = -1
        for i in range(m):
            sel = -1
            for j in range(m):
                if not added[j] and (sel == -1 or w[j] > w[sel]):
                    sel = j
            if i == m - 1:
                best_cut = min(best_cut, w[sel])
                s = v[prev]
                t = v[sel]
                for j in range(m):
                    if j != sel:
                        graph[s][v[j]] += graph[t][v[j]]
                        graph[v[j]][s] += graph[v[j]][t]
                v.pop(sel)
                break
            added[sel] = True
            prev = last
            last = sel
            for j in range(m):
                if not added[j]:
                    w[j] += graph[v[sel]][v[j]]
    return best_cut


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    graph = [[0] * n for _ in range(n)]
    for _ in range(m):
        a = int(data[idx]) - 1; idx += 1
        b = int(data[idx]) - 1; idx += 1
        wt = int(data[idx]); idx += 1
        graph[a][b] += wt
        graph[b][a] += wt

    print(stoer_wagner(n, graph))


main()
計算量: 外側ループは $N-1$ 回マージを行い、各フェーズ（Maximum Adjacency Search）は $O(N^2)$。全体で $O(N^3)$。

Step-by-Step 解説

1隣接行列の構築
多重辺は重みを合算するため graph[a][b] += wt の形で読み込む（= ではなく +=）。
21回のフェーズ
「現在の集合への接続重みが最大の頂点」を貪欲に選んで加えていき、最後に選ばれた頂点 $t$ と直前の頂点 $s$ を確定する。
3cut-of-the-phase の意味
$t$ を孤立させるカットの重みが $s$-$t$ 最小カットの値と一致することが定理により保証される。
4マージと反復
$s,t$ を1頂点に統合し、頂点数が1になるまで繰り返す。記録した値の最小値が答え。

よくあるミス

ミス原因正しい書き方
多重辺を上書き（=）してしまい重みが失われる隣接行列構築時の代入ミスgraph[a][b] += wt で加算する
$s$-$t$ 最小カットを固定端点で $N^2$ 回計算しようとしてTLE専用アルゴリズムを知らないStoer-Wagner法で $O(N^3)$ に削減
マージ時に $s,t$ の行・列を両方更新し忘れる対称行列の更新漏れgraph[s][j]+=graph[t][j] と graph[j][s]+=graph[j][t] の両方を行う
マージ対象を prev ではなく last で行ってしまう変数の意味の取り違えマージ対象は直前に選ばれた頂点 prev、カット対象は最後の頂点 sel

次のステップ

  • 発展: Gomory-Hu Tree（全点対最小カットを $N-1$ 回の最大流で木構造に圧縮）との関係を理解する
  • 発展: 有向グラフの大域最小カットは本アルゴリズムでは解けない（乱択アルゴリズムや $2N$ 回の最大流が必要）
  • 次回予告: Edmonds' Blossom Algorithm（一般グラフ最大マッチング）

自己評価

自分の回答

気づき・メモ