問題
$N$ 頂点 $M$ 辺の無向グラフのグローバル最小カット（最小辺カット数）を求めよ。
制約
$2 \le N \le 500$
$N-1 \le M \le N(N-1)/2$
連結・自己ループなし・多重辺なし
入出力例
入力例 1
4 5
1 2
1 3
2 3
2 4
3 4出力例 1
2ヒント (段階的開示)
ヒント1: 方向性
辺をランダム選択→縮約。頂点数 2 で残った辺数 = カット数候補。成功確率 $\Omega(1/N^2)$。
ヒント2: アプローチ
Karger-Stein なら $\Omega(1/\log N)$ で $O(N^2 \log^3 N)$。シンプル版でも $N=500$ なら $O(N^4 \log N)$ で間に合う。
ヒント3: 実装
隣接行列 + 多重辺カウントで管理。試行回数を増やして信頼度を上げる。
模範解答 (Python)
import sys
import random
import math
input = sys.stdin.readline
def karger_once(adj, n):
active = list(range(n))
while len(active) > 2:
edges = []
for i in range(len(active)):
for j in range(i+1, len(active)):
u, v = active[i], active[j]
if adj[u][v] > 0:
for _ in range(adj[u][v]):
edges.append((u, v))
if not edges:
break
eu, ev = random.choice(edges)
for w in active:
if w != eu and w != ev:
adj[eu][w] += adj[ev][w]
adj[w][eu] = adj[eu][w]
adj[ev][w] = 0
adj[w][ev] = 0
adj[eu][ev] = 0
adj[ev][eu] = 0
active.remove(ev)
u, v = active[0], active[1]
return adj[u][v]
def solve():
N, M = map(int, input().split())
original = [[0]*N for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u -= 1; v -= 1
original[u][v] += 1
original[v][u] += 1
trials = max(50, int(math.ceil(N * N * math.log2(N + 1))))
trials = min(trials, 300)
best = M
for _ in range(trials):
adj = [row[:] for row in original]
result = karger_once(adj, N)
if result < best:
best = result
print(best)
solve()Step-by-Step 解説
1Karger の縮約
辺をランダムに選び両端をマージ、自己ループ削除。頂点 2 で残った辺数 = カット候補。
辺をランダムに選び両端をマージ、自己ループ削除。頂点 2 で残った辺数 = カット候補。
2成功確率分析
$N$ 回の縮約で最小カット辺を1本も選ばない確率 $\ge \binom{N}{2}^{-1}$。
$N$ 回の縮約で最小カット辺を1本も選ばない確率 $\ge \binom{N}{2}^{-1}$。
3繰り返し
$T = \binom{N}{2} \ln N$ で失敗確率 $1/N$ 以下。
$T = \binom{N}{2} \ln N$ で失敗確率 $1/N$ 以下。
4実装注意
多重辺を展開した辺リストからランダム選択は遅いので、重み付きサンプリング推奨。
多重辺を展開した辺リストからランダム選択は遅いので、重み付きサンプリング推奨。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| active 削除漏れ | 縮約後も残る | active.remove(ev) 必須 |
| 自己ループ残り | マージ時に消さない | adj[eu][ev] = adj[ev][eu] = 0 |
| 試行回数不足 | 確率的失敗 | $N^2 \log N$ 程度 |
| adj の参照ミス | 同一オブジェクト使用 | [row[:] for row in original] |
次のステップ
- Karger-Stein で $O(N^2 \log^3 N)$