pyshnograev's blog

Maximum flow
By pyshnograev, 15 years ago, translation, In English
Quite often come across the problem of finding the maximum flow / minimum cut. In this case, we use the Ford-Fulkerson algorithm, or the Edmonds-Karp, sometimes added to this scale, which significantly speeds up the case. The most difficult part of this problem is its attention to the calculation of the flow.

But recently I came across a problem in the archive spoj'a FASTFLOW in which you want to calculate in a very small time a maximum flow with high input data. After writing the solutions in Java and getting TLE I rewrote it in C + +, but again, the Edmonds-Karp algorithm with scaling turned out to be powerless. No other methods I have never found, so the call for help. I think this issue will be of interest not only to me, because usually it does not cover too deep.

Thanks in advance.
  • Vote: I like it
  • +1
  • Vote: I do not like it

15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Try using Dinic's algorithm.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Just checked that push-relabel algorithm with global relabelling heuristic passes the tests.
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it

To solve maximum flow problems,SAP is a good algorithm with high speed and a short code.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my implementation of Dinic's algorithm. I'm getting TLE. What optimization should be done? (Possibly, merging parallel edges?) Please help. (Any bug in my implementation?)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you post your question in all flow-related topics? It only angers people and distracts them from your blogpost.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I'm so sorry. I had posted it before. But I didn't get any answers. So I thought of posting it in a flow related topic. I apologize.

      → Reply