Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Thanks _efer_ | Reply
I've never really been able to understand max flow before. This article is a great help.
Re: Thanks _efer_ (response to post by aussie) | Reply
+1. I've been meaning to learn max flow for a while, but somehow never got around to it. Judging from the questions people ask on the forums, I'm pretty sure I'm not the only one who wanted a tutorial on this.
Re: Thanks _efer_ (response to post by aussie) | Reply
You're welcome! Well, I tried to make the article as comprehensive as possible and to contain a lot of ideas related to this problems! I hope TopCoders will find it useful.
Re: Thanks _efer_ (response to post by _efer_) | Reply
Thanks, that was an awesome article.
I'd like to try out the Rooks question, which SRM was it from?
Re: Thanks _efer_ (response to post by niko) | Reply
RookAttack was TCO 03, Semi Room 4, level 3.

For completeness, the others mentioned were:

Graduation (SRM 200, Div I Level 3)
Parking (SRM 236, Div I Level 3)
DataFilter (TCCC 04 Finals, Level 3)
PlayingCubes (TCO 05 Round 3, Level 1)
Re: Thanks _efer_ (response to post by _efer_) | Reply
Very nice article, by the way :) I learned max flow a long time ago, but it was good to get a review of its applications -- especially bipartite matching, which I've always had trouble with.
Re: Thanks _efer_ (response to post by _efer_) | Reply
Yeah, thanx alot. I havn't read it yet but I did give it a quick overview and it looks as though you did a great job. I can't wait to get into this tutorial and try some of these problems. But I must concentrate on my exams for now.

Oh, by the way, what program did u use to generate those awesome diagrams? I really need to know.
Re: Thanks _efer_ (response to post by crooks_dwayne) | Reply
Those were made in CorelDraw 12
Re: Thanks _efer_ (response to post by _efer_) | Reply
Ok I just read section 2 and, once again, great article.

The only problem I had in both sections was with the pseudo code. It's a bit hard to read (at least for me it is), though it wouldn't take much effort to improve it. It looks to me like you wrote the pseudo code and then went back and changed some of the names to make them more meaningful later, but missed one or two things - e.g. in the first bit of pseudo code in the first section, there's a d that seems to come out of nowhere which I think should actually be path_capacity. If I'm wrong could you tell me what the d actually is supposed to be? Indenting is also a little inconsistent sometimes, and 'single line' comments wrap around to multiple lines. If someone could go through and clean up those few things it would make it much easier to read and make the code worthy of being in with the rest of the article.
Re: Thanks _efer_ (response to post by aussie) | Reply
Yes, you are right, it should have been path_capacity instead of d. I also noticed that problem with the comments and I must agree I find the code a lot harder to read because of that. The same problem arises with longer lines of code (I think that's the indenting-problem you were talking about). I should have made them (both the comments and the code) a little shorter or split them in more lines.
Re: Thanks _efer_ (response to post by _efer_) | Reply
In the 1st section I found a sentence: "This is where the max-flow min-cut theorem comes in and states that the value of the maximum flow through the network is exactly the value of the minimum cut of the network."

Does it mean that the minimum cut is the same as maximum flow? If not, what is the meaning of minimum cut?

In the 2nd section I found a sentence: "We learned earlier how to find the value of the min-cut and how to find an arbitrary min-cut." But I can't find the explanation about min-cut earlier...?

Btw, nice article... But I still confused with the meaning of minimum-cut :D
Re: Thanks _efer_ (response to post by felix_halim) | Reply
Re: Thanks _efer_ (response to post by felix_halim) | Reply
I found the answer for my previous post in here (

Then I have another question for 2nd section for figure9. The picture is for T = 2. But I failed to understand the meaning of figure9: How come 1 becomes 3? and 5 becomes 11?

Obviously 1*2 is 2 (not 3), and 5*2 is 10 (not 11) ??

I need more explanation for the figure9.

Thanks for writing the article, it gives me new skills :D
Re: Thanks _efer_ (response to post by felix_halim) | Reply
Yes, the value of the minimum-cut equals the value of the maximum-flow. Also, a method that finds the minimum-cut is described (in the last two paragraphs of the section "How to solve it"): consider a vertex reachable if there is a path in the residual network from the source to it. Then, take the edges with the property that their starting point is reachable and their ending point is not. Notice that this edges are filled to capacity but the converse is obviously not true: not every edge filled to capacity is necessarily part of the minimum-cut.
Re: Thanks _efer_ (response to post by felix_halim) | Reply
Please read more carefully:

Notice what happens if we multiply each edge capacity with a constant T. Clearly, the value of the maximum flow is multiplied by T, thus the value of the minimum cut is T times bigger than the original. A minimum cut in the original network is a minimum cut in the modified one as well. Now suppose we add 1 to the capacity of each edge. Is a minimum cut in the original network a minimum cut in this one? The answer is no, as we can see in Figure 8 shown below, if we take T = 2.

There is a tiny error there, it should have been Figure 9 instead of Figure 8.
[ 1 2 ]    NEXT >