Day 008-Q1 | 二部グラフマッチング

問題

$N$ 人の学生と $M$ 個のプロジェクトがある。各学生はいくつかのプロジェクトを担当できる。各プロジェクトは1人の学生しか担当できない。最大で何人の学生にプロジェクトを割り当てられるか求めよ。

制約

$1 \le N, M \le 500$

$0 \le K_i \le M$

$1 \le p_{i,j} \le M$

入出力例

入力例 1

出力例 1

入力例 2

2 1
1 1
1 1

出力例 2

ヒント (段階的開示)

ヒント1: 方向性

二部グラフの最大マッチング問題。

ヒント2: アプローチ

ハンガリアン法（増加路法）。各学生についてDFSで増加路を探し、見つかれば割り当てを更新する。

ヒント3: 誘導

def dfs(v, visited):
    for u in graph[v]:
        if not visited[u]:
            visited[u] = True
            if match[u] == -1 or dfs(match[u], visited):
                match[u] = v
                return True
    return False

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]

    for i in range(N):
        line = list(map(int, input().split()))
        k = line[0]
        for j in range(1, k + 1):
            graph[i].append(line[j] - 1)

    match = [-1] * M

    def dfs(v, visited):
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                if match[u] == -1 or dfs(match[u], visited):
                    match[u] = v
                    return True
        return False

    result = 0
    for i in range(N):
        visited = [False] * M
        if dfs(i, visited):
            result += 1

    print(result)

solve()

Step-by-Step 解説

1二部グラフの構築
学生 $i$ → プロジェクト $j$ の有向辺。

2増加路探索（DFS）
未割り当てなら割り当てる、割り当て済みなら現担当を別へ移せるか再帰探索。

3計算量
$O(NM)$。各学生について $O(M)$ の DFS。

よくあるミス

ミス	原因	正しい書き方
visited を共有してしまう	学生ごとにリセットが必要	`visited = [False] * M` をループ内で初期化
match を学生側に持つ	プロジェクト側で持つと簡単	`match[project] = student`

次のステップ

発展問題: 最小頂点被覆（König 定理: 最小頂点被覆 = 最大マッチング）

自己評価

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

Day 008-Q1 — 二部グラフマッチング

問題

制約