概要

\(N\) 人の参加者全員にプレゼントを1個ずつ配るとき、希望通りのプレゼントを受け取って満足する参加者の人数を最大化する問題です。これは最大フロー（最大流）を用いた二部マッチング問題として解くことができます。

考察

重要な気づき

まず、すべての参加者にプレゼントを1個ずつ渡す必要がありますが、満足する人数を最大化したいというのが目的です。

ここで重要な観察があります：

• 希望のプレゼントをもらえた参加者 → 満足
• 希望外のプレゼントをもらった参加者 → 不満足（でもプレゼントは受け取る）

プレゼントの総数は \(N\) 以上なので、全員に何かしら配ることは必ず可能です。したがって、満足する人を最大化する部分と残りの人に余ったプレゼントを配る部分を分けて考えられます。

なぜ貪欲法では難しいか

例えば、参加者Aと参加者Bが同じプレゼント（1個しかない）を希望している場合、どちらに渡すかによって全体の満足者数が変わります。単純な貪欲法では最適な割り当てを見逃す可能性があります。

解決方針：二部マッチングへの帰着

「参加者」と「プレゼントの種類」の間の二部グラフで、容量付きの最大マッチングを求めれば、それがそのまま満足する参加者の最大人数になります。不満足な参加者には余ったプレゼントを適当に配ればよく、プレゼント総数 \(\geq N\) なので必ず可能です。

アルゴリズム

最大フロー（Edmonds-Karp法、BFSベースのFord-Fulkerson法）を用いて解きます。

フローネットワークの構築

以下のようにグラフを構築します：

Source(S) → プレゼント種類i → 参加者j → Sink(T)

具体的には：

1. Source \(S\) から プレゼント種類ノード \(i\)（\(i = 1, \ldots, M\)）へ、容量 \(B_i\) の辺を張る
   • 各種類のプレゼントは \(B_i\) 個まで配れる
2. プレゼント種類ノード \(i\) から 参加者ノード \(j\) へ、容量 \(1\) の辺を張る（参加者 \(j\) が種類 \(i\) を希望している場合のみ）
   • 参加者が希望しているプレゼントのみ繋ぐ
3. 参加者ノード \(j\) から Sink \(T\) へ、容量 \(1\) の辺を張る
   • 各参加者は最大1個のプレゼントで満足する

例で理解する

\(N=3, M=2\)、プレゼントは種類1が2個、種類2が2個。参加者1は種類1を希望、参加者2は種類1,2を希望、参加者3は種類2を希望の場合：

S --2--> [種類1] --1--> [参加者1] --1--> T
S --2--> [種類2] --1--> [参加者2] --1--> T
                  --1--> [参加者3] --1--> T
（種類1→参加者2、種類2→参加者2 の辺もあり）

このネットワークの最大フロー = 3 となり、全員が満足できます。

なぜこれで正しいか

• フローが流れた参加者 = 希望のプレゼントを受け取れた（満足した）参加者
• 各プレゼント種類の容量制約 \(B_i\) が守られる
• 各参加者は高々1個で満足（Sink への容量が1）
• フローが流れなかった参加者には余りのプレゼントを配ればよい（総数 \(\geq N\) で保証）

計算量

• ノード数: \(V = M + N + 2\)（最大約1002）

• 辺数: \(E = O(M + NM + N) = O(NM)\)（最大約250,000）

• Edmonds-Karp法の計算量は \(O(VE^2)\) ですが、二部マッチングでは実際にはフローの上限が \(N\) であるため \(O(N \cdot E) = O(N^2 M)\)

• 時間計算量: \(O(N^2 M)\)（最大約 \(500^2 \times 500 = 1.25 \times 10^8\) 程度）

• 空間計算量: \(O(NM + V)\)（グラフの辺とノードの記憶）

実装のポイント

• ノード番号の割り当て: Source を \(0\)、プレゼント種類を \(1 \sim M\)、参加者を \(M+1 \sim M+N\)、Sink を \(M+N+1\) とすると管理しやすい。

• 逆辺の管理: 最大フローでは逆辺（残余グラフ）が必要です。defaultdict(lambda: defaultdict(int)) を使うと、辺の追加・残余容量の更新が簡潔に書けます。

• BFSでの増加路探索: Edmonds-Karp法ではBFSで最短増加路を見つけることで、計算量の保証が得られます。

• プレゼントの種類番号が1-indexed: 入力で与えられる種類番号を0-indexedに変換して、ノード番号 \(c+1\) としてプレゼントノードに対応させています。

  ソースコード

from collections import defaultdict, deque

def max_flow(graph, source, sink, n):
    def bfs(source, sink, parent):
        visited = set([source])
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in visited and graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return True
                    queue.append(v)
        return False
    
    total_flow = 0
    parent = {}
    while bfs(source, sink, parent):
        path_flow = float('inf')
        s = sink
        while s != source:
            u = parent[s]
            path_flow = min(path_flow, graph[u][s])
            s = u
        total_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
        parent = {}
    return total_flow

def solve():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    B = []
    for i in range(M):
        B.append(int(input_data[idx])); idx += 1
    
    wishes = []
    for j in range(N):
        K = int(input_data[idx]); idx += 1
        cs = []
        for k in range(K):
            cs.append(int(input_data[idx]) - 1); idx += 1
        wishes.append(cs)
    
    # We want to maximize the number of satisfied participants.
    # Each participant must receive exactly 1 present. Total presents >= N.
    # A participant is satisfied if they receive one of their wished presents.
    
    # Model as max flow:
    # Source S, Sink T
    # For each present type i: node P_i
    # For each participant j: two nodes J_sat_j (satisfied path) and J_any_j (any path)
    # Actually, let's think more carefully.
    
    # We can use a flow network to find maximum matching of participants to wished presents,
    # subject to capacity constraints on presents, then check feasibility that remaining
    # participants can be assigned remaining presents.
    
    # But we need to ensure ALL participants get a present. So we need to binary search or 
    # directly model it.
    
    # Direct flow model:
    # S -> each present type i with capacity B[i]
    # Each present type i -> participant j (if j wishes i) with capacity 1
    # Each participant j -> "satisfied" node -> T with capacity 1
    # But we also need all participants to get a present (unsatisfied ones too).
    
    # Actually: maximize satisfied subject to everyone getting a present.
    # Since presents >= N, and we just need to count max satisfied, we can model:
    # Max bipartite matching between participants and their wished present types (with capacities).
    # The matching gives satisfied count. Unmatched participants get leftover presents.
    # We need to verify unmatched participants can get presents from remaining stock.
    # But with N,M <= 100, we can just find max matching with capacity and then greedily check.
    
    # Actually, since sum(B) >= N, and any unmatched participant can receive any leftover present,
    # the max number of satisfied participants = max matching in bipartite graph (participants to present types with capacities).
    
    # Flow network:
    # Source = 0
    # Present nodes: 1..M
    # Participant nodes: M+1..M+N
    # Sink = M+N+1
    
    S = 0
    T = M + N + 1
    graph = defaultdict(lambda: defaultdict(int))
    
    for i in range(M):
        graph[S][i + 1] += B[i]
    
    for j in range(N):
        for c in wishes[j]:
            graph[c + 1][M + 1 + j] += 1
        graph[M + 1 + j][T] += 1
    
    result = max_flow(graph, S, T, M + N + 2)
    print(result)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。