Calls and repairers
At rush hour orders come in to a repair service. Each order has its own list of repairers who can do that kind of work and get there in time; in that hour a repairer takes at most one order. The dispatcher has to assign as many orders as possible. There may be noticeably more orders than repairers, and then some orders inevitably wait for the next hour.
The data are made up: a generator with a fixed seed.
Input
The first line holds n and m (1 ≤ n, m ≤ 50,000), the number of orders and repairers. Then n lines: a number k and k distinct repairer numbers from 1 to m suitable for the order (0 ≤ k ≤ m). The sum of all k is at most 150,000.
Output
The largest number of orders that can be assigned at the same time.
Examples
Example 1
4 3 2 1 2 1 1 2 2 3 1 3
3
Example 2
5 4 2 1 2 1 1 1 2 2 1 2 2 3 4
3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is the maximum matching in the bipartite graph “orders and repairers”. Why does a greedy assignment, giving each order the first free repairer, go wrong on the first sample?
2Hint 2
Kuhn's algorithm with a new depth-first search from each order is correct. How much does the search cost for an order that cannot be assigned, and how many such orders are there in the third test?
3The idea
You need the Hopcroft–Karp algorithm. A failed search in Kuhn's algorithm walks everything the alternating paths from the order reach, often almost the whole graph, and changes nothing. When there are half as many repairers as orders, there are tens of thousands of failed searches, and the time becomes quadratic. Hopcroft–Karp handles all free orders at once in one phase: one breadth-first search builds the layers, one depth-first pass along the layers finds many paths. There are few phases, at most about 2√V.
4Walkthrough
A phase. The breadth-first search starts from all free orders at once: order → any suitable repairer → the order that repairer currently holds, and so on. If a free repairer turns up along the way, an augmenting path exists, and the distances to orders are the layers. Then from each free order look for a path depth-first, but only from layer d to layer d + 1. Flip a path once found: each order on it moves to the next repairer, and the last repairer was free. A vertex from which no path was found is marked as a dead end until the end of the phase, so it is never entered twice, and the whole phase costs O(E).
Why there are few phases. After a phase the shortest augmenting path becomes longer. After √V phases all remaining augmenting paths are longer than √V, and in the difference between the current and a maximum matching they share no vertices, so there are at most √V of them, and each further phase adds at least one. Hence O(E √V).
The simple remedy for Kuhn, not resetting the marks after a failed search, helps only in part: after every successful search the marks are still reset, and the measurement in the article shows it stays quadratic on the same data.
4+Solution
5Complexity
O(E √V), where V = n + m and E is the total length of the lists. Kuhn is O(V E).
6Common mistakes
- Greed. The first order takes a repairer the second cannot do without: the first sample.
- Kuhn head-on. Correct, but the third test has 50,000 orders for 25,000 repairers, and almost every second search fails.
- Recursion. Paths in the alternating graph can be long; in Python your own stack is better.