Overview

A problem where we distribute presents to participants and maximize the number of people whose wishes are fulfilled. This can be modeled as a maximum flow problem on a bipartite graph.

Analysis

This problem is a combinatorial optimization problem of deciding “to whom” and “which present” to distribute. A naive approach would be to try all combinations, but since the number of participants \(N\) and the number of present types \(M\) can be up to 500, exhaustive search would result in an explosion of computation and is not practical.

A key observation is the following constraints: “each participant receives at most one present” and “each present can only be distributed up to the prepared quantity.” Additionally, a participant is satisfied when they “receive any one of the presents they wished for.”

To optimally perform such “matching,” it is effective to formulate it as a maximum flow problem on a bipartite graph.

Specifically, we construct the following graph:

• Left vertices: Participants (\(1\) to \(N\))
• Right vertices: Present types (\(1\) to \(M\))
• Draw an edge with capacity 1 from source \(S\) to each participant (each person receives only one)
• Draw an edge with capacity 1 from each participant to the presents they wish for (choosing from their wished items)
• Draw an edge from each present to sink \(T\) with capacity \(B_i\) (the quantity of that present) (quantity constraint)

Computing the maximum flow on this constructed graph gives us the “maximum number of satisfied participants.”

Algorithm

This problem can be solved as a Max Flow Problem. Specifically, we solve it using Dinic’s algorithm.

Steps:

1. Graph Construction

   • Vertex set: Source \(S\), participants \(1..N\), presents \(1..M\), sink \(T\)
   • Edges:
     • \(S \rightarrow\) each participant: capacity 1
     • Each participant \(\rightarrow\) their wished presents: capacity 1
     • Each present \(\rightarrow T\): capacity \(B_i\)

2. Compute Maximum Flow

   • Use an algorithm such as Dinic’s algorithm to compute the maximum flow from source to sink.

3. Output the Answer

   • The value of the obtained maximum flow is the maximum number of satisfied participants.

Complexity

• Time complexity: \(O(N \cdot M^2)\) (Complexity of maximum flow computation using Dinic’s algorithm. Precisely \(O(E \cdot V^2)\), but it is bounded by the graph size in this problem)
• Space complexity: \(O(N + M + E)\) (Memory required for the adjacency list representation of the graph)

Implementation Notes

• Be careful with vertex numbering in the graph (e.g., participants are 1 to N, presents are N+1 to N+M, etc.)

• When adding edges, reverse edges must also be set up simultaneously (required by the nature of maximum flow algorithms)

• In Dinic’s algorithm implementation, the flow consists of building a level graph with bfs and searching for augmenting paths with dfs

• Be cautious of Python’s recursion limit (especially when DFS depth is large)

  Source Code

from collections import deque

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    B = [0] * (M + 1)
    for i in range(1, M + 1):
        B[i] = int(data[idx]); idx += 1

    # グラフを作る
    # left: 1..N (参加者), right: 1..M (プレゼント)
    # ソース: 0, シンク: N+M+1

    # グラフの隣接リスト表現（辺の容量付き）
    # 使用する頂点番号: 0（source）, 1..N（参加者）, N+1..N+M（プレゼント）, N+M+1（sink）

    INF = 10**9
    source = 0
    sink = N + M + 1

    # グラフ構築
    # 隣接リスト: graph[v] = [(to, cap, rev_index)]
    graph = [[] for _ in range(N + M + 2)]

    def add_edge(fr, to, cap):
        graph[fr].append([to, cap, len(graph[to])])
        graph[to].append([fr, 0, len(graph[fr]) - 1])

    # source -> 参加者: 容量1
    for i in range(1, N + 1):
        add_edge(source, i, 1)

    # 参加者 -> 希望するプレゼント: 容量1
    for i in range(1, N + 1):
        K = int(data[idx]); idx += 1
        for _ in range(K):
            c = int(data[idx]); idx += 1
            add_edge(i, N + c, 1)

    # プレゼント -> sink: 容量B[c]
    for c in range(1, M + 1):
        add_edge(N + c, sink, B[c])

    # 最大流を求める（Dinic法）
    def bfs():
        level[:] = [-1] * (N + M + 2)
        queue = deque([source])
        level[source] = 0
        while queue:
            v = queue.popleft()
            for to, cap, _ in graph[v]:
                if level[to] == -1 and cap > 0:
                    level[to] = level[v] + 1
                    queue.append(to)
        return level[sink] != -1

    def dfs(v, t, f):
        if v == t:
            return f
        while iter[v] < len(graph[v]):
            to, cap, rev = graph[v][iter[v]]
            if cap > 0 and level[v] < level[to]:
                d = dfs(to, t, min(f, cap))
                if d > 0:
                    graph[v][iter[v]][1] -= d
                    graph[to][rev][1] += d
                    return d
            iter[v] += 1
        return 0

    def max_flow():
        flow = 0
        while True:
            if not bfs():
                break
            iter[:] = [0] * (N + M + 2)
            while True:
                f = dfs(source, sink, INF)
                if f == 0:
                    break
                flow += f
        return flow

    level = [-1] * (N + M + 2)
    iter = [0] * (N + M + 2)
    result = max_flow()
    print(result)

solve()

This editorial was generated by qwen3-coder-480b.