
Hello! Could someone explain me how to solve this problem http://www.topcoder.com/stat?c=problem_statement&pm=4731&rd=8016 using MaxFlow (problem as an example from the tutorial)? I settled with a maximum bipatile matching algorithm, but it doesn't work (at least in my implementation). So what is I am doing: To check whether it is possible to combine a word with given set of cubes, I am using the following algorithm (let's take the example 1 from the problem statement): Word: "BIRD", Cubes: {"ABCDEF", "DEFGHI", "OPQRST", "MNZLSA", "QEIOGH", "IARJGS"} I am creating a flow network with the set of letters L, the set of cubes R. So, common scheme:
S  L  R  T.
There is an edge between vertices Li and Rj (1 <= i <= L, 1 <= j <= R) if cube Rj contains letter Li. All the edges have capacity 1. So, in my understanding, there can be flow 4, so we can combine the cubes to get word "BIRD" as follows: (lettercube (0based):'B'0, 'I'4, 'R'5, 'D'1). And ok, this is a right answer according to the example answer.
But my algo does not give me MaximumMatching 4. I am using EndmondsKarp algo. At each iteration I am looking for a shortest augmenting path in the residual network, and assign a flow along this path. But what if first found path contains letter 'B' + cube 0, and second found path contains letter 'I'  cube 1 ("DEFGHI") (both have the same length)? In that case I will not be able to have letter 'D' as only cubes 0 and 1 contain it, and they are already used!
So, summarizing, my difficulty is: when I see the network of the given case, it seems to be a maximum bipatile matching, and EndmondsKarp algo should work in this case, but it doesn't. Did I miss something important? Thanks! 