Police Chase-CSES graph Section

1

(CSES - Police Chase) .This problem involves minimum no of edges to be removed in order to prevent thief from reaching vertex 1 to n.
Actually i am stuck at the part where we have to find the edges.
From what i was doing i thought total edges to be removed would be equal to total augmenting paths but unable to find which edges . please help @carre @ssjgz @everule1 @ssrivastava990

2

anybody??

3

https://cp-algorithms.com/graph/edmonds_karp.html#toc-tgt-5

4

thanks but i have seen that can u elaborate more.
Actually i am taking capacity of each edge as 1 but when i am finding any augmenting path i am decreasing the capacity by one due to which that path cannot be used more.But how to find which particular edge on that path is critical edge

5

Well, you just have to use DFS from 1, on unused edges. All edges between the nodes you visit on this dfs, and the ones you dont, are the cut edges.

1 Like
6

but how will that give the minimum
consider
1 2
1 3
2 4
4 5
4 6
here we need to remove only 2-4 how would the above will give this

7

It will give you 1 -> 2 as the only edge which is also correct.

8

sorry there was also an edge between 3 and 2
thanks for help till now as i am new to flows please can u tell what changes should to my code .
Link to code https://cses.fi/paste/049adcd6790c036f11c565/

9

if u want explanation of anyhting in the code i will tell u . Basically it is edmond karp only

10

What I see is you are finding a path, and then breaking the last edge of the path. That is the same as removing k edges from node n. That is not necessarily even a cut. Construct the cut how I described it.

1 Like
11

Thanks i will try to implement can u explain the above more elaboratly or with the help of a good example