psywoo's blog

By psywoo, history, 7 weeks ago, In English

Problem Statement :

You are given a Directed graph with N Vertices and M edges(it may or may not have cycles, it doesn't have multiple edges or self loops) and two vertices Start and End. You need to find the minimum number of vertices you need to block so that there is no way to reach Vertex End from the vertex Start. You cannot block the Start and End vertex.

Constraints :

4 <= N <= 1e5

3 <= M <= min(2e5 , N * (N — 1))

1 <= Start, End <= N

PS : Problem Source not known, But its Definitely not from a live contest :)

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

You think of mcmf to find the amount of chokepoints in the graph, this reminds me of something similar to https://www.spoj.com/problems/BANKROB/ But for those constraints I'm not really sure

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It looks like a mincut problem, but it seems that dinic and HLPP aren't able to solve this one with $$$n\le 10^5$$$...

$$$n\le 100$$$ version is ABC239G.

»
7 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

never mind, just realized it would not work.

»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

You can solve this with regular flow (no need for the slower mcmf as others have suggested). Your graph is just the input graph with edges set to infinity and nodes split, with the weight across one node being equal to 1. The min cut across this graph is what you're looking for. That's always equal to the max flow, which can be calculated with Dinic's algorithm.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you exactly choose the node for which all weights across it are equal to 1?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For every node except the start node, you split that node into two new nodes. The edge from the entrance to that node to the exit of that node will have weight 1.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

does this code work? CODE