A transport plan
There are k sources of cargo and d stations. Source i holds ai units, station j needs bj, and in all there is exactly as much as is needed. Cargo can be carried only along the m routes in the table; a route from source i to station j costs c per unit and carries any amount. Distribute all the cargo so that the total cost is smallest.
The third test is A. N. Tolstoi’s problem of 1930: 10 sources, 68 stations and 155 routes with distances in kilometres from the table reprinted by Alexander Schrijver; cargo is in hundreds of tonnes.
Input
The first line holds k, d and m (1 ≤ k ≤ 60, 1 ≤ d ≤ 600, 1 ≤ m ≤ 6000). The second holds k numbers ai, the third d numbers bj (from 1 to 10⁵; both sums are the same and at most 10⁶). Then m lines i j c: a route from source i to station j costing c per unit (0 ≤ c ≤ 10⁴). A pair i, j occurs at most once, and all the cargo can be distributed along these routes.
Output
The smallest total cost. It may not fit in 32 bits.
Examples
Example 1
2 3 5 3 2 2 2 1 1 1 4 1 2 6 2 2 3 2 3 5 1 3 9
22
Example 2
2 2 3 1 1 1 1 1 1 1 1 2 2 2 1 3
5
Limits
- Time · Python
- 14000 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
The cheapest route first? Look at the second example: the cheap route from the first source to the first station takes away the second station’s only source. How do you correct a shipment already made?
2Hint 2
Build a network: source → cargo sources (capacity ai) → stations (routes from the table, cost c) → sink (capacity bj). A flow of value Σbj of least cost is needed. What should the reverse arc cost?
3The idea
This is a minimum-cost flow. The reverse arc costs minus the cost of the forward one: cancelling a shipment saves its price. Grow the flow from zero, each time along the cheapest path from the source to the sink in the residual network. By the theorem on successive shortest paths a negative circle never appears in the residual network, which means each intermediate flow is the best for its value, and so is the last one.
4Walkthrough
Arcs are stored in pairs: a and a ^ 1, the reverse with capacity 0 and cost −c. A route from a source to a station gets capacity “any amount”; the sum of all demands is enough. The shortest path is found by Dijkstra on reduced costs c + π(u) − π(v); after the search, add the distances to the potentials. The initial potentials are zeros, as all costs are non-negative. Send along the path found as much as its narrowest arc allows, and add to the answer amount × (π(t) − π(s)): after the update this is the cost of the path in real prices.
In Tolstoi’s test it comes to 3,950,520 hundred tonne-kilometres, that is, 395,052 thousand, the same as his plan.
4+Solution
5Complexity
Each path saturates a source arc, a station arc or cancels a shipment. On these tests there are at most one and a half times as many paths as sources and stations together: 89 against 78 in Tolstoi’s problem, 933 against 610 in the sixth test. Each search is O(E log V). Bellman–Ford with a queue instead of Dijkstra also passes here: such a network has almost no circles, as the measurement in the article shows.
6Common mistakes
- The cheapest route in the table first, the “least cost method”. This is
wrong.py: without cancellations it either overpays, as in the first example (23 instead of 22), or gets stuck when a station has no sources left, as in the second. In Tolstoi’s problem it leaves six stations without cargo this way. - Dijkstra without potentials. After the first cancellation the residual network has arcs of negative cost, and Dijkstra on real prices may go wrong.
- 32 bits. Up to a million units of cargo at a price up to ten thousand: the sum can reach 10¹⁰.
Algorithms behind it
O(F · E log V)
2 problems
GRA
Algorithm
Dijkstra's algorithm
Shortest paths from one vertex in a weighted graph without negative edges.
O((V + E) log V)
3 problems