799. The Last Courier Home
A depot has n couriers and n parcels. Courier i needs c[i][j] minutes to deliver
parcel j and return. Every courier takes exactly one parcel and every parcel goes to exactly one
courier. They all set off at the same time, so the round is over when the SLOWEST of them gets
back.
Print the smallest possible finishing time.
4 9 2
7 1 8 -> 4
5 6 3
Courier 1 takes parcel 1 (4 minutes), courier 2 takes parcel 2 (1 minute), courier 3 takes parcel 3 (3 minutes). The round takes 4. No pairing does better, because every pairing that avoids the 4 forces the 9, the 7 or the 8 on somebody.
## Why the greedy answers are wrong
Giving each courier their own fastest parcel does not work; two couriers may want the same one. Sorting the whole table and taking the cheapest pairs in order does not work either, because an early cheap pair can leave two couriers fighting over one remaining parcel. Adding up the total and minimising THAT is a different problem again: this one cares only about the maximum.
Trying every pairing is exact and hopeless. With n = 60 there are 60! of them.
## What a candidate answer buys you
Fix a finishing time T. Courier i is allowed parcel j exactly when c[i][j] <= T. That
leaves a two-sided graph, couriers on one side, parcels on the other, and the question becomes:
can every courier be paired with a different parcel using only the allowed pairs?
which is a perfect matching. Kuhn's algorithm answers it by giving each courier an augmenting
path in turn: walk the parcels this courier may take, and if one is free take it, otherwise ask
its current owner to move elsewhere. Each courier costs one pass over the table, so the whole
check is O(n^3).
This is the lesson of the problem. The predicate does not have to be a counting loop. It can be a whole graph algorithm, and the binary search neither knows nor cares.
## Why the predicate is monotone
Raising T only adds allowed pairs. A matching that exists under T uses pairs that are still
allowed under any larger T, so it survives untouched. Feasible finishing times form a suffix
and the answer is the first of them.
## The bounds
Every finishing time IS one of the entries of the table, because the round ends when some particular courier gets back. So collect the distinct entries, sort them, and binary search the INDEX. The largest entry always works, since any pairing at all finishes by then.
## The boundary that breaks a careless implementation
The used marks inside Kuhn's search must be reset for EVERY courier, not once for the whole
check. Sharing them across couriers makes the search give up early and reports impossible
matchings as impossible when they are not. The four by four table with a heavy diagonal is in the
tests for that reason.
## Width
Table entries reach 10^9, which fits in a signed 32-bit integer, and the algorithm only ever
compares them against the candidate rather than adding them together. The courier count is at
most 60. Nothing in this problem overflows, and saying so is cheaper than wondering.
## Related problems
Problem 794 also answers a threshold question with a graph structure rather than a counter, and problem 798 puts a breadth first search inside the same kind of search.
## Cost
Time O(n^3 log n). Space O(n^2).
Constraints - `1 ≤ n ≤ 60` - `1 ≤ c[i][j] ≤ 10^9`
Input
The first line contains one integer n.
Each of the next n lines contains n integers; the jth value of line i is c[i][j], the minutes courier i needs for parcel j.
Output
Print one integer, the smallest possible time at which the last courier gets back. Print it alone on one line, with no units.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.