Some days ago I came across a nice problem: Fat Hobbits . The problem's input is a directed acyclic graph G = (V, E) with additional property that if (u, v) is in E and (v, z) is in E then (u, z) is also in E, i.e. it has transitive closure, and asks for a maximum size subset of vertices IND such that if v is in IND and u is in IND, then none of (u, v) and (v, u) are in E.
Problem seemed difficult for me at first, but finally I could solve it by modeling it as a min-cut problem. The problem can be easier solved once you know Dilworth's Theorem and how to prove it.
From time to time you will see problems which can be solved using max-flow min-cut algorithms. To see some more problems, see topcoder tutorial Maximum Flow, Section 2 and also these lecture notes. I also remember some more from other online judges: Dual Core CPU, Intervals, and many more which I don't remember right now.
You'd probably ask how can you detect if a given problem can be solved using Max-Flow? I also can't detect many such algorithms, but probably the answer is: Either by experience or by guessing. After you see many problems which can be solved using max-flow, you can easily invent some new max-flow formulations for some other problems. If you can't do this, you can probably guess a formulation and try to prove or disprove it, since most of formulations aren't strange. Guessing is an art, a beautiful art :-) But try to prove your guesses, otherwise you might waste your time with debugging wrong solutions.
Problem seemed difficult for me at first, but finally I could solve it by modeling it as a min-cut problem. The problem can be easier solved once you know Dilworth's Theorem and how to prove it.
From time to time you will see problems which can be solved using max-flow min-cut algorithms. To see some more problems, see topcoder tutorial Maximum Flow, Section 2 and also these lecture notes. I also remember some more from other online judges: Dual Core CPU, Intervals, and many more which I don't remember right now.
You'd probably ask how can you detect if a given problem can be solved using Max-Flow? I also can't detect many such algorithms, but probably the answer is: Either by experience or by guessing. After you see many problems which can be solved using max-flow, you can easily invent some new max-flow formulations for some other problems. If you can't do this, you can probably guess a formulation and try to prove or disprove it, since most of formulations aren't strange. Guessing is an art, a beautiful art :-) But try to prove your guesses, otherwise you might waste your time with debugging wrong solutions.
