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

Unable to solve Max-Flow problem on Spoj
Автор arun_prasad, история, 8 лет назад, По-английски

I was trying to solve this problem on Spoj . Click Here.

After spending a couple of hours on this I could only come up with a dfs solution which obviously got TLE.

Then I looked for help online and i found this quora solution QUORA SOLUTION .

Can someone tell me with an example and proof of the extra nodes to be added and why maxflow should be 2 for it to be right?

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

»
8 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

well , when you add that extra node and connect it to Naboo and Coruscant , you can have at most two vertex-disjoint paths from Tatooine to that extra node , and if you have two paths , you have these two paths :

1) Tatooine -> Naboo

2) Tatooine -> Coruscant

and these two paths are vertex-disjoint , so you have this path : Naboo -> Tatooine -> Coruscant

and also , suppose you have less than two vertex-disjoint paths from Tatooine to the extra node , It is obvious that you don't have the Naboo -> Tatooine -> Coruscant path , (if you have , there would be 2 vertex-disjoint paths from Tatooine to the extra node , which is not the case )

→ Ответить