Блог пользователя psywoo

Автор psywoo, история, 22 месяца назад, По-английски

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 :)

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

never mind, just realized it would not work.

»
22 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

does this code work? CODE