Overview

This is a problem where we distribute one present to each of the \(N\) participants and want to maximize the number of participants who are satisfied (i.e., receive a present they wished for). This can be solved as a bipartite matching problem using maximum flow.

Analysis

Key Observation

First, we need to give exactly one present to every participant, but our objective is to maximize the number of satisfied people.

Here is an important observation:

• A participant who receives a wished-for present → satisfied
• A participant who receives a present they didn’t wish for → unsatisfied (but still receives a present)

Since the total number of presents is at least \(N\), it is always possible to distribute something to everyone. Therefore, we can separately consider the part that maximizes satisfied people and the part that distributes leftover presents to the remaining people.

Why a Greedy Approach Is Difficult

For example, if participant A and participant B both wish for the same present (of which only one exists), the overall number of satisfied people changes depending on who receives it. A simple greedy approach may miss the optimal assignment.

Solution Strategy: Reduction to Bipartite Matching

By finding a maximum matching with capacities in the bipartite graph between “participants” and “present types,” the result directly gives the maximum number of satisfied participants. Unsatisfied participants can be given leftover presents arbitrarily, which is always possible since the total number of presents is \(\geq N\).

Algorithm

We solve this using maximum flow (Edmonds-Karp method, a BFS-based Ford-Fulkerson method).

Constructing the Flow Network

We construct the graph as follows:

Source(S) → Present type i → Participant j → Sink(T)

Specifically:

1. Add an edge from Source \(S\) to present type node \(i\) (\(i = 1, \ldots, M\)) with capacity \(B_i\)
   • Each type of present can be distributed up to \(B_i\) times
2. Add an edge from present type node \(i\) to participant node \(j\) with capacity \(1\) (only if participant \(j\) wishes for type \(i\))
   • Only connect presents that the participant wishes for
3. Add an edge from participant node \(j\) to Sink \(T\) with capacity \(1\)
   • Each participant is satisfied by at most one present

Understanding with an Example

\(N=3, M=2\), with 2 presents of type 1 and 2 presents of type 2. Participant 1 wishes for type 1, participant 2 wishes for types 1 and 2, and participant 3 wishes for type 2:

S --2--> [Type 1] --1--> [Participant 1] --1--> T
S --2--> [Type 2] --1--> [Participant 2] --1--> T
                   --1--> [Participant 3] --1--> T
(Edges from Type 1→Participant 2 and Type 2→Participant 2 also exist)

The maximum flow of this network = 3, meaning all participants can be satisfied.

Why This Is Correct

• Participants with flow = participants who received a wished-for present (satisfied)
• The capacity constraint \(B_i\) for each present type is respected
• Each participant is satisfied by at most one present (capacity to Sink is 1)
• Participants without flow can be given leftover presents (guaranteed since total \(\geq N\))

Complexity

• Number of nodes: \(V = M + N + 2\) (at most about 1002)

• Number of edges: \(E = O(M + NM + N) = O(NM)\) (at most about 250,000)

• The complexity of the Edmonds-Karp method is \(O(VE^2)\), but in bipartite matching the flow is bounded by \(N\), so it is actually \(O(N \cdot E) = O(N^2 M)\)

• Time complexity: \(O(N^2 M)\) (at most about \(500^2 \times 500 = 1.25 \times 10^8\))

• Space complexity: \(O(NM + V)\) (storing edges and nodes of the graph)

Implementation Notes

• Node numbering: It is convenient to assign Source as \(0\), present types as \(1 \sim M\), participants as \(M+1 \sim M+N\), and Sink as \(M+N+1\).

• Reverse edge management: Maximum flow requires reverse edges (residual graph). Using defaultdict(lambda: defaultdict(int)) allows concise edge addition and residual capacity updates.

• BFS augmenting path search: In the Edmonds-Karp method, finding the shortest augmenting path via BFS provides the complexity guarantee.

• Present type numbers are 1-indexed: The type numbers given in the input are converted to 0-indexed and mapped to present nodes as node number \(c+1\).

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.