Need help — Modelling into a flow problem.

Правка en1, от rupav, 2020-04-17 10:12:08

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://mirror.codeforces.com/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.

Теги flow networks, maxflow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский rupav 2020-04-17 10:12:08 1040 Initial revision (published)