arun_prasad's blog

Unable to solve Max-Flow problem on Spoj
By arun_prasad, history, 10 years ago, In English

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?

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

»
10 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

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 )

→ Reply