最大二部匹配(ford-fulkerson)

Question

我当时正在读http://www.geeksforgeeks.org/maximum-bipartite-matching/和algorithm，并且很难理解。这个例子似乎是假设每个工作只能接受一个人，每个人想要一份工作。我想知道如果v集的容量>1(可以雇用多个人来完成该工作)和u集>1(每个人都想要一个以上的工作)，那么算法/代码会发生什么变化？

Answer 1

为了允许多个人分配给作业，您只需将边缘容量从Jobs修改为Terminal (类似于Niklas .在his comment中的描述，但不完全是这样)。

如下所示：

​

​

从Source到People的1和从People到Jobs的1的容量保证了一个人只会为一份工作被选中(因为他们可以贡献的最大流量是1)。但是，从> 1到Jobs到Terminal的容量允许为该工作分配多个人。

如果一个人也能完成1项以上的工作，那么从Source到Person的最大流量就会增加那么多：

​

​

其中，i、j、k和x是值为>= 1的整数的暂存体。

这里需要记住的关键是，People左边的流容量决定了他们可以接受多少个作业，而Jobs右边的流容量决定了分配给这个任务的人有多少。中间的能力不应改变。