最大二分匹配(ford-fulkerson)

Question

我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm,我很难理解.似乎这个例子假设每个工作只能接受1个人,每个人想要1个工作.我想知道算法/代码将如何改变,例如,如果v set的容量> 1(可以为该工作雇佣多人)并且u set> 1(每个人想要超过1个工作)？

Answer 1

为了让作业分配有不止一个人,你只修改边容量从Jobs到Terminal(类似尼克拉斯B.如何描述他的意见,但不完全是.)

像这样:

1从能力Source到People,并从1 People到Jobs保证,一个人仅会于一个工作选择(因为最大流量,他们可以整体贡献为1).然而,容量> 1从Jobs以Terminal允许多于一个人可以被分配到工作.

如果一个人也可以执行超过1个工作,那么最大流量Source将Person增加该数量:

其中i,j,k,和x是替身与值的整数>= 1

这里需要记住的关键是,左边的流量People决定了他们可以承担多少工作量,右边的流量能力Jobs决定了可以分配多少人的工作量.中间的能力不应该改变.