justHusam's blog

Max-flow min-cut problem
By justHusam, 10 years ago, In English

I’m trying to solve this problem, I tried two different ways to solve it, but I got wrong answer for both of them.

  • First way: delete from the graph all edges that don’t belong to a path of length <= k, then run max-flow min-cut. code
  • Second way: run max-flow min-cut using Ford–Fulkerson method, and I will stop when the shortest path between the source and the sink is bigger than 2*k (here I multiply k by 2 because there’s an extra edge for every node to save its own capacity). code

Please can anyone tell me what’s wrong in my ideas? And can anyone give an idea to solve this problem?

UPD: Any help please?

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

»
9 years ago, # |
← Rev. 6   Vote: I like it +10 Vote: I do not like it

https://ideone.com/F7sfh4 this is my solution based on your code. But i did some changes.

First, you should find if there is any way that some path <=k pass from u to v. You can find that with running two times shortest path algorithm, one from the No.1 bus station and one from the No.N bus station.Then exhaust every edge, if (from1[u]+fromn[v]+1<=k) then there is some path pass from u to v <=k.

Next, If there is a way (or some) pass from u to v. You should addedge(u+n,v) Then you can simply output the maxflow.

Sorry for my poor English.

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

After some wa, i could solve the problem, using Floyd for make the graph and max flow to search the answer, i hope this help you.

this is my solution.

→ Reply