Day 101-Q2 — Karger-Stein法（乱択最小カットの分割統治高速化）

問題

無向連結マルチグラフの最小カットを、Karger-Stein法の手続きに厳密に従って計算せよ。真の乱数の代わりに、あらかじめ与えられた整数列 $R$ を使って全ての「ランダムな選択」を決定的に行う。

手続き（ポインタ`ptr`は全再帰呼び出しで共有）:

1. 現在の代表元集合の個数を $n$ とする。$n\le6$なら全探索で最小カットを求めて返す。
2. そうでなければ $t=\lceil1+n/\sqrt2\rceil$ とし、現在の状態を複製して$t$まで縮約（`ContractUntil`）し再帰した結果`cutA`、再び元の状態を複製して同様に求めた結果`cutB`の$\min$を返す。

ContractUntil: アクティブな辺（両端点の代表元が異なる辺、元の順序）の本数`cnt`について、`idx=R[ptr]%cnt`で1本選び両端点の代表元を統合。目標個数になるまで繰り返す。

$n\le6$の全探索: 代表元を昇順に並べ$r_0$を含む非空真部分集合$S$（$S$が全体集合になる場合を除く$2^{n-1}-1$通り）ごとに、片方の端点のみ$S$に属するアクティブ辺の本数を数え最小値を返す。

入力形式

N M
u_1 v_1
:
u_M v_M
L
r_1 ... r_L

制約

入出力例

7 9
1 2
2 3
1 3
4 5
5 6
6 7
7 4
4 6
3 4
2
8 0

1

2つの三角形/密グラフ状クラスタ{1,2,3}と{4,5,6,7}が橋(3,4)で連結。真の最小カット=1（橋）。branchAは橋を潰して最良2止まりだが、branchBはクラスタ内部の辺を潰して橋を温存し真の値1を発見、min(2,1)=1が出力される。

概念図

ヒント（段階的開示）

def fastmincut(parent):
    roots = {find(parent, v) for v in range(1, N + 1)}
    n = len(roots)
    if n <= 6:
        return brute_force(parent)
    t = math.ceil(1 + n / math.sqrt(2))
    parentA = parent[:]
    contract_until(parentA, t)
    cutA = fastmincut(parentA)
    parentB = parent[:]   # 「元の」parentから再度複製
    contract_until(parentB, t)
    cutB = fastmincut(parentB)
    return min(cutA, cutB)

模範解答 (Python)

📋 コピーimport sys
import math


def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    edges = []
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        edges.append((u, v))

    L = int(data[idx]); idx += 1
    R = [int(x) for x in data[idx:idx + L]]; idx += L

    ptr = [0]

    def find(parent, x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def active_edges(parent):
        return [(u, v) for (u, v) in edges if find(parent, u) != find(parent, v)]

    def contract_until(parent, target):
        while True:
            roots = {find(parent, v) for v in range(1, N + 1)}
            if len(roots) <= target:
                return
            act = active_edges(parent)
            cnt = len(act)
            i = R[ptr[0]] % cnt
            ptr[0] += 1
            u, v = act[i]
            ru, rv = find(parent, u), find(parent, v)
            parent[rv] = ru

    def brute_force(parent):
        roots = sorted({find(parent, v) for v in range(1, N + 1)})
        n = len(roots)
        act = active_edges(parent)
        best = float('inf')
        for mask in range((1 << (n - 1)) - 1):
            S = {roots[0]}
            for i in range(n - 1):
                if (mask >> i) & 1:
                    S.add(roots[i + 1])
            cnt = 0
            for (u, v) in act:
                ru, rv = find(parent, u), find(parent, v)
                if (ru in S) != (rv in S):
                    cnt += 1
            if cnt < best:
                best = cnt
        return best

    def fastmincut(parent):
        roots = {find(parent, v) for v in range(1, N + 1)}
        n = len(roots)
        if n <= 6:
            return brute_force(parent)
        t = math.ceil(1 + n / math.sqrt(2))
        parentA = parent[:]
        contract_until(parentA, t)
        cutA = fastmincut(parentA)
        parentB = parent[:]
        contract_until(parentB, t)
        cutB = fastmincut(parentB)
        return min(cutA, cutB)

    parent0 = list(range(N + 1))
    print(fastmincut(parent0))


solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: アルゴリズムを$T$回独立実行し最小値を採用することで成功確率をさらに高める
• 発展: 優先度付きキューベースの縮約実装で$O(N^2\log^3N)$を達成する設計を調べる
• 次回予告: de Bruijnグラフ上のオイラー閉路構築（Hierholzer法）

自己評価

自分の回答

気づき・メモ