Peregrine_Falcon's blog

Need some basic practice problems about Max-Flow
By Peregrine_Falcon, history, 6 years ago, In English

I just learned Ford-Fulkerson Algorithm for Maximum Flow Problem with BFS/DFS. I solved one problem from lightoj.com.

But I couldn't find any basic problem to practice the basic algorithm.

If someone can provide me some very basic problem, by practicing them I'll get used to the basic concept & coding also learn something I'll be really very grateful. I've some problems but those are not basic.

Thank You.

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

Comments Comments (13)
| Write comment?
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Ford fulkerson's algo is likely not enough to get you through many Max Flow problems (I will let you find out why). Learn edmond karp's algo instead.

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

    I'll be glad if you help me.

    I'll learn it, but I want to solve some problems of this Algorithm first. Just to get more clearer about this and have a better coding skill for this. Thank You.

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

      You can try out the problems in CP3 that are classified in uhunt as Max Flow (you need to type in your UvA username to see this). Those are problems that I would say are basic.

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

        Sorry for disturbing you again. Uhunt I can only find Network Flow. Is this it? Standard Max Flow Problem (Edmonds Karp's) ?They can be solved by Fulkerson? Thank you.

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

          The thing is, you can pass many test cases using ford fulkerson, but a TLE verdict is likely to be all you'll get even if your algo is correct because there is a particular kind of graph that is challenging for ford fulkerson's algo. If you just want to try out the ford fulkerson's algo but don't care about the verdict, you can try solving the problems on uhunt. If you get TLE, that is likely a sign that your algo is correct, but the input has the special graph that I described above.

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

            Can I ask for any easily described resource of edmond karp's tutorial? I learned Fulkerson from Topcoder. Thank You.

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

              Edmond Karp's algo is essentially same as ford fulkerson's algo. Just that the method for finding an augmenting path is BFS instead of DFS.

              Anyway, Edmond Karp's algo is a very well-known algo. You can easily find many research papers and academic presentations on it if you google.

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

                I used BFS to solve Max-Flow. But I can also solve this by DFS. For 15 test cases and 100 nodes and 5000 edges it took 0.020. Lightoj 1153. Is it enough to solve those UVA? Thank You.

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

                Thank You for your help.

                → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=565

Try out some of these problems. You will probably not get them. Struggle with them, and then try to find solutions online.

The biggest thing with flow is figuring out how to construct the graph and motivate the flow to get the answer you want. This is very hard to do at first, but there's a few tricks involved that will get you through many, many problems. When you look up solutions online, some of them will describe somewhat inefficient graphs (say they use 3n nodes instead of only n necessary nodes, or something). See if you can modify the graphs and still get AC, because it will improve your understanding of how to create such graphs.

Flow problems are really hard at first. They get easier, I promise. Honestly, don't worry about coding the actual flow algorithm. Find some template that's good because 90% of the time you won't modify the actual flow algo.

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Ford-Fulkerson is rather a method — find augmenting paths and fill them while you can also filling with reverse flow if needed, and all max-flow algorithms like Edmond Karp build on this technique by using a good heuristic to find these paths.

→ Reply