Overview

This is a problem where we distribute presents to participants and want to maximize the number of people who are satisfied by receiving their desired present. This problem can be solved by reducing it to a maximum flow problem (network flow) on a graph.

Analysis

The problem statement says “it is allowed to distribute presents that were not desired” and “it is always possible to distribute to everyone (the total number of presents is at least \(N\)).” Therefore, we simply need to find “the maximum number of people who can receive their desired present.” For participants who are not matched, we can distribute leftover presents arbitrarily, satisfying the condition that everyone receives a present.

The problem of associating participants with present types can be viewed as a bipartite graph matching problem. However, since each present type has a quantity limit of \(B_i\), instead of a simple maximum bipartite matching algorithm, it is best to model this as a maximum flow problem with capacities on edges.

Algorithm

We use Dinic’s algorithm, a fast algorithm for computing maximum flow. We construct a network (directed graph) with vertices and edges (capacities) as follows:

1. Vertex preparation:

   • Prepare a super source as the overall starting point and a super sink as the endpoint.
   • Prepare vertices corresponding to each of the \(N\) participants.
   • Prepare vertices corresponding to each of the \(M\) present types.

2. Edge construction:

   • From the super source to each participant, add an edge with capacity \(1\). (Because each participant can receive only \(1\) present)
   • From each participant to the types of presents they desire, add edges with capacity \(1\).
   • From each present type to the super sink, add an edge with capacity \(B_i\). (Because the quantity limit for each present is \(B_i\))

By computing the maximum amount of flow (maximum flow) from the super source to the super sink on this graph, the resulting value directly gives “the maximum number of satisfied participants.”

Complexity

• Time complexity: \(O(E \sqrt{V})\) Let the number of vertices be \(V = N + M + 2\) and the number of edges be \(E \le N + M + N \times M\). The general complexity of Dinic’s algorithm is \(O(V^2 E)\), but for bipartite graph structures like this one (where edge capacities are \(1\) or only specific vertices have capacity \(B_i\)), it runs very efficiently, completing in approximately \(O(E \sqrt{V})\). Given the constraints, \(V \approx 1000\) and \(E \approx 250000\), which is well within the time limit.
• Space complexity: \(O(V + E)\) This is the memory required to store the graph’s vertex and edge information as an adjacency list.

Implementation Notes

• Changing the recursion limit: When implementing the depth-first search (DFS) of Dinic’s algorithm in Python, to prevent errors from deep recursion, it is necessary to raise the limit with sys.setrecursionlimit(200000).

• Efficient management of reverse edges: To efficiently perform flow pushback operations (updating the residual graph), edge information is stored in a list format of [destination vertex, capacity, index of reverse edge], allowing immediate mutual capacity updates.

• Fast I/O: Since the number of input lines and elements can be large, using sys.stdin.read().split() to read all input at once and processing it by advancing an index (idx) significantly reduces execution time.

  Source Code

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

---

This editorial was generated by gemini-3.1-pro-thinking.