Day 019-Q3 | 一般マッチング（Blossom Algorithm）

問題

$N$ 頂点 $M$ 辺の一般無向グラフ $G$ の最大マッチングの辺数と、具体的な辺集合を出力せよ。

制約

$2 \le N \le 500$

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

多重辺・自己ループなし

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

二部グラフなら augmenting path で解けるが、一般グラフでは奇数サイクル（花 = blossom）が発生する。

ヒント2: アプローチ

Edmondsの花アルゴリズム：未マッチング頂点からBFSで増加路を探す。奇数サイクルを発見したら収縮（shrink）。$O(N^3)$。

ヒント3: 誘導

def augment(root):
    parent = [-1] * (N+1)
    base = list(range(N+1))
    # BFS で増加路 or blossom を探す

模範解答 (Python)

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

def solve():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v); adj[v].append(u)

    match = [-1] * (N + 1)

    def augment(root):
        parent = [-1] * (N + 1)
        base = list(range(N + 1))
        used = [False] * (N + 1)
        blossom = [False] * (N + 1)
        used[root] = True
        queue = deque([root])

        def lca(a, b):
            visited = set()
            while True:
                a = base[a]; visited.add(a)
                if match[a] == -1: break
                a = parent[match[a]]
            while True:
                b = base[b]
                if b in visited: return b
                b = parent[match[b]]

        def mark_path(v, b, child):
            while base[v] != b:
                blossom[base[v]] = True
                blossom[base[match[v]]] = True
                parent[v] = child
                child = match[v]
                v = parent[match[v]]

        while queue:
            v = queue.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if parent[to] == -1:
                    if match[to] == -1:
                        parent[to] = v
                        u = to
                        while u != -1:
                            pv = parent[u]
                            ppv = match[pv]
                            match[u] = pv
                            match[pv] = u
                            u = ppv
                        return True
                    parent[to] = v
                    used[match[to]] = True
                    parent[match[to]] = to
                    queue.append(match[to])
                elif used[to] and parent[to] != v:
                    curbase = lca(v, to)
                    for i in range(N + 1): blossom[i] = False
                    mark_path(v, curbase, to)
                    mark_path(to, curbase, v)
                    for i in range(1, N + 1):
                        if blossom[base[i]]:
                            base[i] = curbase
                            if not used[i]:
                                used[i] = True
                                queue.append(i)
        return False

    res = 0
    for v in range(1, N + 1):
        if match[v] == -1:
            if augment(v): res += 1

    print(res)
    for v in range(1, N + 1):
        if match[v] != -1 and v < match[v]:
            print(v, match[v])

solve()

Step-by-Step 解説

1増加路（Augmenting Path）
マッチング辺と非マッチング辺が交互に現れる、両端が未マッチング頂点を繋ぐパス。マッチングを反転すれば +1（Berge の定理）。

2Blossom（花）
奇数サイクルのうち、根が未マッチングな交互経路に接続しているもの。BFS で奇数サイクルを発見。

3Shrink（収縮）
Blossom を一つの super vertex に縮約。縮約後のグラフで増加路を探し、見つかれば展開。

4計算量
各 augment $O(N^2)$、合計 $O(N^3)$。N=500 で約 $1.25 \times 10^8$ 回。

よくあるミス

ミス	原因	正しい書き方
blossom 判定の条件	`parent[to] != -1` だけでは不十分	`used[to]` も確認
base 配列の更新漏れ	shrink 後に base を更新しない	blossom 内の全頂点の base を curbase に統一
増加路復元の方向	parent 配列の向き間違い	augment 後の while で match を更新

次のステップ

発展: 一般重み付きマッチング（Hungarian Algorithm の一般グラフ版）

自己評価

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

Day 019-Q3 — 一般マッチング（Blossom Algorithm）

問題

制約