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 th eminimum cut that seperates s from t. We have to divide the graph into two parts one group containing source and the other one containing 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 Algo for max flow 1. Starting with flow of 0 2. Repeatly finding the Augmented Path from the source to the sink in the residual graph. It is just a simple path having the avaliable capacity in the edge. (I considered the flow of the path to be 1). 3. Use BFS to find the augmented path, additionally calculate the minimum flow in the augmented path. 4. 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 that the number of minimum streets to block = maximum flow we just calculated from the theorem
To find the streets to cut: 1. Perform BFS/DFS over the residual graph from the source such that capacity of the edge is positive. 2. This detects the set of the nodes which are with the source in it. 3. Now just iterate over this collection of set and find the other node reachable from these nodes in the original graph such that the child node is not in the this set. These edges are out final streets which we have to cut.
