Couriers and orders
A city has n free couriers and n ready orders. For each pair the cost is known: how many metres the courier has to drive along the streets to the order. Each courier takes exactly one order, and each order goes to exactly one courier. Assign the orders so that the sum of the costs is smallest.
In two tests the costs are real distances along the streets of Almaty from random intersections to cafés from OpenStreetMap, as in the article; in the rest they are random and deliberately awkward tables.
Input
The first line holds n (1 ≤ n ≤ 150). Then come n lines of n integers: in line i at position j, the cost of the pair “courier i, order j”, from 0 to 109.
Output
The first line holds the smallest sum. The second holds n numbers: the order number for couriers 1, 2, …, n. If there are several best assignments, print any.
Examples
Example 1
3 1 2 9 2 9 9 9 9 3
7 2 1 3
Example 2
4 4 4 4 4 4 4 4 4 1 4 4 4 4 4 4 1
10 3 2 1 4
Limits
- Time · Python
- 8000 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
In the first example take the shortest pair, then the shortest of the remaining ones, and so on. How much did you get? Can it be less?
2Hint 2
Pick a number for each courier and each order so that for any pair the sum of the two numbers does not exceed the cost. Why then does no assignment cost less than the sum of all these numbers? And what if an assignment uses only pairs where the sum equals the cost?
3The idea
The Hungarian algorithm from the article. The potentials ui of couriers and vj of orders always satisfy ui + vj ≤ cij, and the assignment is built only along tight pairs, where this is an equality. Couriers are added one at a time: from a new courier a tree grows along tight pairs through taken orders; when there are not enough tight pairs, the potentials of the tree’s couriers grow by δ, the smallest reduced cost from the tree outwards, and those of the tree’s orders decrease by δ. A new tight pair appears, and the old ones are not spoilt. As soon as a free order turns up in the tree, the path to it is flipped. At the end all pairs are tight, and by the theorem from the article the sum is the smallest.
4Walkthrough
The short form with dummy column 0 and the arrays minv (the smallest reduced cost to each order outside the tree) and way (where we came to it from) is the same as in the article’s listing. In the first example greed takes the pair (1, 1) for 1, then (3, 3) for 3, and has to give courier 2 order 2 for 9: 13 in all. The best is 2 + 2 + 3 = 7: courier 1 takes order 2, courier 2 order 1.
Sums go up to 150 · 109: Go needs int64.
4+Solution
5Complexity
O(n3): for each of the n couriers at most n potential shifts of O(n) each. With n = 150 that is about three million simple operations.
6Common mistakes
- Shortest pair first. The last couriers are left with expensive orders: the first example.
- The nearest free courier for each order. The same mistake from the other side.
- Trying permutations. 150! options; even with n = 12 that is already half a billion.
- Infinity at the limit of the type. If in Go you take
math.MaxInt64as “infinity”, subtracting δ from it and adding potentials overflow;math.MaxInt64 / 4is enough. In Pythonfloat('inf')works: subtracting δ does not spoil it, and the potentials themselves stay integers.