arun_prasad's blog

Unable to solve Max-Flow problem on Spoj
By arun_prasad, history, 8 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

»
8 years ago, # |
← 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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    hey thanks :) actually I had misunderstood the quora solution . now its clear. thanks for replying anyway :) +1d!

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I had one more question. Is it necessary to learn the working of dinic? or is edmond karp sufficient? i dont understand the working of dinic. but i just know how to use it. is it alright?

    → Reply