rupav's blog

Need help — Modelling into a flow problem.
By rupav, history, 5 years ago, In English

I am trying to solve 1214D by making the free and impassable cells as nodes, source as (1, 1) and sink as (n, m). And then joining only those edges for which flow is possible (between cell and its first right neighbor, if both free; cell and its first down neighbor, if both free) with capacity 1. Now finding the max flow in this problem should give me either 0, 1, 2, which should be the answer I thought originally. But this approach fails on a tc 44, i.e.

4 5

.....

....#

.....

..#..

(My code o/p is 2, but it should be 1, by blocking (3, 4) cell)

I realized why it is failing, but my question is how to model it then as a flow problem. A good alternate solution is https://codeforces.me/blog/entry/69563?#comment-541155 . But I would like to solve it as a flow problem. What should be the approach while solving these types of flow problems? Thanks.

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You need to compute the number of vertex independent paths and not number of edge independent paths. The construction you have made computes number of edge independent paths. For computing number of vertex independent paths from node $$$S$$$ to $$$T$$$ in a graph first create a new graph having twice the number of nodes as the original graph.(Each node $$$U$$$ is divided into two parts $$$U_{in}$$$ and $$$U_{out}$$$), if node U is allowed in the original graph then add an edge with capacity 1 from $$$U_{in}$$$ to $$$U_{out}$$$, in case node $$$U$$$ is source or sink the capacity of edge should be infinite. Also for each edge in the original graph $$$U$$$->$$$V$$$ create an edge $$$U_{out}$$$ to $$$V_{in}$$$ with infinite(or very high) capacity. Now run maxflow from $$$S_{in}$$$ to $$$T_{out}$$$.

check this for better understanding.(The weight for internal edges in S and T is shown to be 1 but it should be infinite which is clear in the code)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot. Let me know if I correctly understood this:

    So basically the motivation behind creating the vertex independent paths is to get the blocking vertex.

    In my attempt, because of making edge independent paths only, I was trying to find those edges, removing which there will be no flow from source to sink.

    But now with your construction, max flow algorithm will also give those edges removing which will block the flow, but now those edges represent the vertices too. So eventually we will be getting the blocking vertices/edges. But since you have marked edges of the original graph with infinite capacity, max flow will find blocking vertices only and that actually is the aim of the problem.

    Isn't it?

    → Reply