Leaving the stadium
After a match, cars leave the car parks near the stadium and spread out across the city. The transport service wants to know how many streams of cars can leave at the same time, if each lane carries one stream: how many lanes at best lead from the car parks to the exits from the district. Lanes are counted by direction: a street may have, say, two lanes one way and one the other, and a one-way street has no lanes in the opposite direction at all.
Three tests are real streets of central Almaty from OpenStreetMap with the number of lanes in each direction: the car parks are all crossings within 400 metres of the Central Stadium or within 500 metres of the Green Bazaar, and the exits are all crossings more than three or two and a half kilometres from them.
Input
The first line holds n and m (2 ≤ n ≤ 8000, 1 ≤ m ≤ 12,000), the number of crossings and of street pieces. Then m lines a b f g: a piece of street between crossings a and b, on which f lanes lead from a to b and g lanes from b to a (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ f, g ≤ 10). There may be several pieces between the same crossings. Then a line: k and k numbers of crossings at the car parks; then a line: l and l numbers of exit crossings. These sets do not intersect, k, l ≥ 1.
Output
One number: the greatest number of lanes along which streams can go at once from the car parks to the exits: each lane of each street piece is taken by at most one stream, and each stream is a route from some car park to some exit.
Examples
Example 1
6 7 1 2 3 0 1 3 2 0 2 4 2 0 2 5 2 0 3 4 3 0 4 6 2 0 5 6 3 0 1 1 1 6
4
Example 2
7 7 1 3 2 2 2 3 1 1 3 4 1 0 3 5 2 1 4 6 2 2 5 7 1 1 5 4 1 1 2 1 2 2 6 7
3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 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 a maximum flow problem: the capacity of an arc is the number of lanes in that direction. What to do if there are many sources and sinks?
2Hint 2
The first example: if flow is sent along paths found and never cancelled, you get 3, while the answer is 4. Which path needs to be found third?
3The idea
Add a common source with arcs of infinite capacity to all the car parks and a common sink with the same arcs from all the exits. Each street piece gives two arcs: a → b of capacity f and b → a of capacity g. The maximum flow from the common source to the common sink is the answer: by integrality the flow splits into routes of one lane each.
4Walkthrough
The Edmonds–Karp algorithm: find a path in the residual network by breadth-first search and send the smallest residual along it. Add each arc in a pair with a reverse one of capacity 0, numbered 2i and 2i + 1; then the partner of arc a is a ^ 1. Sending x along an arc means decreasing its residual by x and increasing its partner’s residual by x.
Reverse arcs are mandatory here. In the first example, after the paths 1 → 2 → 4 → 6 (two lanes) and 1 → 2 → 5 → 6 (one), there are no free paths along the streets themselves, but the residual network has the path 1 → 3 → 4 → 2 → 5 → 6: it goes along the arc 4 → 2 against flow already sent, cancels one lane of 2 → 4 and gives the fourth.
Several street pieces between the same crossings get in the way of nothing: they are simply several arcs.
4+Solution
5Complexity
O(V E²) in the worst case, but here there are no more paths than the value of the answer, and it is small: on the real streets of Almaty, 20 and 22 lanes. Each path is one breadth-first traversal in O(V + E).
6Common mistakes
- No reverse arcs. The greedy flow gets stuck: the first and seventh tests.
- One arc per street piece. Lanes in different directions are different arcs; merging them into one undirected arc means allowing travel against one-way traffic.
- Finite capacities at the common source. If an arc to a car park is given capacity 1, the answer runs up against the number of car parks.
- No path at all. The answer is 0, the eighth test.