maximum bipartite matching (ford-fulkerson)

Question

I was reading http://www.geeksforgeeks.org/maximum-bipartite-matching/ and http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm and am having trouble understanding. It seems the example is under the assumptions that each job can only accept 1 person and each person wants 1 job. I was wondering how the algorithm/code would change if for example, the v set had capacity > 1 (can hire multiple people for that job) and the u set > 1 (each person wants more than 1 job)?

Answer 1

To allow jobs to have more than one person assigned to them, you'd only modify edge capacities from Jobs to Terminal (Similar to how Niklas B. described in his comment, but not exactly.)

Like this:

The capacities of 1 from the Source to the People, and 1 from People to Jobs guarantees that a person will only ever be selected for one job (because the maximum flow that they can contribute overall is 1). However, the capacities > 1 from Jobs to Terminal allows that more than one person can be assigned to that job.

If a person can perform also more than 1 job, then the max flow from Source to Person increases by that amount:

Where i, j, k, and x are stand-ins for integers with values >= 1

The key thing to remember here is that flow capacities to the left of People dictate how many jobs they may take, and the flow capacities to the right of Jobs dictate how many people may be assigned that job. The capacities in the middle should not change.