概要

参加者にプレゼントを配る際、希望のプレゼントをもらって満足する人数の最大値を求める問題です。この問題は、グラフの最大流問題（ネットワークフロー）に帰着して解くことができます。

考察

問題文には「希望していないプレゼントを配ることも許される」「全員に配ることは必ず可能（プレゼントの総数が \(N\) 以上）」とあります。したがって、単に「希望のプレゼントを配れる最大人数」を求めればよく、マッチングしなかった参加者には余ったプレゼントを適当に配ることで、全員に配るという条件を満たせます。

参加者とプレゼントの種類を紐付ける問題は、二部グラフのマッチングとして捉えることができます。しかし、各プレゼントの種類には \(B_i\) 個という個数制限があるため、単純な最大二部マッチングアルゴリズムではなく、辺に容量を持たせた最大流問題としてモデル化するのが最適です。

アルゴリズム

最大流を求める高速なアルゴリズムである Dinic法 を使用します。 以下のように頂点と辺（容量）を設定したネットワーク（有向グラフ）を構築します。

1. 頂点の準備:

   • 全体の開始点となる 超源点（source） と、終点となる 超終点（sink） を用意します。
   • \(N\) 人の参加者に対応する頂点を用意します。
   • \(M\) 種類のプレゼントに対応する頂点を用意します。

2. 辺の張り方:

   • 超源点から各参加者へ、容量 \(1\) の辺を張ります。（各参加者がもらえるプレゼントは \(1\) つであるため）
   • 各参加者から、希望するプレゼントの種類へ、容量 \(1\) の辺を張ります。
   • 各プレゼントの種類から超終点へ、容量 \(B_i\) の辺を張ります。（各プレゼントの個数制限が \(B_i\) 個であるため）

このグラフ上で超源点から超終点へ流せる最大の量（最大流）を計算すると、その値がそのまま「満足する参加者の人数の最大値」となります。

計算量

• 時間計算量: \(O(E \sqrt{V})\) 頂点数を \(V = N + M + 2\)、辺数を \(E \le N + M + N \times M\) とします。Dinic法の計算量は一般に \(O(V^2 E)\) ですが、今回のような二部グラフの形（辺の容量が \(1\) や特定の頂点のみ \(B_i\)）では非常に高速に動作し、実質的に \(O(E \sqrt{V})\) 程度で完了します。制約から \(V \approx 1000\)、\(E \approx 250000\) であり、十分に実行時間制限に間に合います。
• 空間計算量: \(O(V + E)\) グラフの頂点と辺の情報を隣接リストとして保持するためのメモリ量です。

実装のポイント

• 再帰上限の変更: PythonでDinic法の深さ優先探索（DFS）を実装する場合、再帰が深くなってエラーになるのを防ぐため、sys.setrecursionlimit(200000) で上限を引き上げておく必要があります。

• 逆辺の効率的な管理: フローを押し戻す処理（残余グラフの更新）を高速に行うため、辺の情報を [行き先の頂点, 容量, 逆辺のインデックス] のリスト形式で持たせ、お互いの容量を即座に更新できるように工夫しています。

• 高速な入出力: 入力の行数や要素数が多くなるため、sys.stdin.read().split() を使って入力を一括で読み込み、インデックス（idx）を進めながら処理することで実行時間を大幅に短縮しています。

  ソースコード

import sys

sys.setrecursionlimit(200000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    B = [int(x) for x in input_data[2:2+M]]
    
    idx = 2 + M
    
    source = 0
    sink = N + M + 1
    
    graph = [[] for _ in range(N + M + 2)]
    
    def add_edge(u, v, c):
        graph[u].append([v, c, len(graph[v])])
        graph[v].append([u, 0, len(graph[u]) - 1])
        
    for i in range(1, N + 1):
        add_edge(source, i, 1)
        
    for i in range(1, M + 1):
        add_edge(N + i, sink, B[i-1])
        
    for i in range(1, N + 1):
        K = int(input_data[idx])
        idx += 1
        for _ in range(K):
            c = int(input_data[idx])
            idx += 1
            add_edge(i, N + c, 1)
            
    level = [-1] * (N + M + 2)
    
    def bfs():
        for i in range(N + M + 2):
            level[i] = -1
        level[source] = 0
        queue = [source]
        for u in queue:
            lu = level[u] + 1
            for v, c, rev in graph[u]:
                if c > 0 and level[v] == -1:
                    level[v] = lu
                    queue.append(v)
        return level[sink] != -1

    ptr = [0] * (N + M + 2)
    
    def dfs(u, f):
        if u == sink:
            return f
        lu = level[u]
        for i in range(ptr[u], len(graph[u])):
            ptr[u] = i
            v, c, rev = graph[u][i]
            if c > 0 and lu < level[v]:
                pushed = dfs(v, f if f < c else c)
                if pushed > 0:
                    graph[u][i][1] -= pushed
                    graph[v][rev][1] += pushed
                    return pushed
        return 0

    flow = 0
    while bfs():
        for i in range(N + M + 2):
            ptr[i] = 0
        while True:
            pushed = dfs(source, 1000000000)
            if not pushed:
                break
            flow += pushed
            
    print(flow)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。