The "minimum number of streets to block" directly redirects us to Max Flow Min Cut Theorem.
It says the maximum flow we send from a source s to sink t is exactly equal to the capacity of the minimum cut that separates s from t. We have to divide the graph into two parts: one group containing the source and the other one containing the sink. A capacity of the cut is the sum of capacities of the edges going from the source's set to the sink's set.
My Approach
By using Edmonds-Karp Algorithm for max flow:
- Starting with flow of 0
- Repeatedly finding the Augmented Path from the source to the sink in the residual graph. It is just a simple path having the available capacity in the edge. (I considered the flow of the path to be 1).
- Use BFS to find the augmented path, additionally calculate the minimum flow in the augmented path.
- If the path is found and flow > 0 then add the path flow to maximum flow. Update the residual graph: decrease the capacity along the path and increase at opposite path. This finally leads to the maximum flow of the graph.
One thing we know is that the number of minimum streets to block = maximum flow we just calculated from the theorem.
To find the streets to cut:
- Perform BFS/DFS over the residual graph from the source such that capacity of the edge is positive.
- This detects the set of nodes which are with the source in it.
- Now just iterate over this collection of nodes and find the other node reachable from these nodes in the original graph such that the child node is not in this set. These edges are our final streets which we have to cut.
