Routes with no shared crossing
A security service is preparing the passage of a motorcade from one crossing in the city to another. So that one accident or one road closure does not ruin everything, it wants to prepare as many backup routes as possible in advance, and no two routes may pass through the same crossing, except, of course, the start and the end. How many such routes can be prepared?
Three tests are real streets of central Almaty from OpenStreetMap, all streets two-way; the start and end are the crossings nearest to landmarks where at least three streets meet.
Input
The first line holds n, m, s and t (2 ≤ n ≤ 10,000, 0 ≤ m ≤ 25,000, 1 ≤ s, t ≤ n, s ≠ t): the number of crossings, the number of streets, the start and the end. Then m lines a b: a street between crossings a and b, along which one can drive both ways. A street does not connect a crossing to itself, and there is at most one street between two crossings.
Output
The greatest number of routes from s to t, no two of which pass through a common crossing other than s and t. A street directly from s to t, if there is one, is a route too.
Examples
Example 1
8 8 1 8 1 2 1 3 2 4 3 4 4 5 4 6 5 8 6 8
1
Example 2
7 10 1 7 1 2 2 7 1 3 3 4 4 7 1 7 3 5 5 6 6 7 2 4
3
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 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
If routes were only forbidden to share streets, a flow with capacity 1 on each street would be enough. Why does such a flow give 2 in the first example, while the answer is 1?
2Hint 2
The limit has to be put on a crossing, while a flow can limit only edges. How do you turn a vertex into an edge?
3The idea
Split each crossing v into two vertices: an entrance vin and an exit vout, joined by an arc of capacity 1. A street a — b becomes the arcs aout → bin and bout → ain. Now at most one unit of flow passes through a crossing, and the maximum flow from sout to tin is the number of routes without common crossings.
4Walkthrough
Why the flow equals the answer. Any set of routes without common crossings gives a flow of the same value: send one unit along each route, and no arc “entrance → exit” gets more than one. Conversely: the capacities are integers, so there is a maximum flow of zeros and ones, and such a flow splits into paths from s to t. Two paths cannot pass through one crossing, because the arc vin → vout lets one unit through. The start and the end are not split, as they have no limit, or, equivalently, their arcs get a large capacity.
The flow is found by Edmonds–Karp: each path adds one, and there are no more paths than the degree of s. The answer also equals the smallest number of crossings whose closure makes it impossible to get from s to t; this is Menger’s theorem. On the real streets of Almaty the answer is 3 in two tests, while one route leads to Kok-Tobe: it has a crossing through which all paths pass.
If two routes meet at a crossing but arrive and leave by different streets, counting without splitting vertices accepts both. The seventh test is built like this: forty chains, every two of which meet at a common middle point; there are 40 routes without common streets and 20 without common crossings.
4+Solution
5Complexity
There are 2n vertices and 2n + 4m arcs (with reverse ones). Each breadth-first traversal is O(n + m), there are at most the answer plus one traversals, and the answer is at most the degree of s. In all, O(deg(s) · (n + m)).
6Common mistakes
- Not splitting vertices. You get the number of routes without common streets: the first and seventh tests.
- Splitting the start and end with capacity 1. Then the answer is always at most one.
- A street as one arc. The streets are two-way, so arcs in both directions are needed.
- No path. The answer is 0, the ninth test.