algorithm - 最大二分匹配（ford-fulkerson）

Question

我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm并且无法理解。似乎这个例子是在假设每个工作只能接受 1 人并且每个人想要一份工作的情况下。我想知道如果 v 集的容量 > 1（可以为该工作雇用多个人）和 u 集 > 1（每个人想要超过 1 个工作），算法/代码将如何变化？

Answer 1

要允许为工作分配多个人，您只需将边缘容量从 修改Jobs为Terminal（类似于 Niklas B. 在他的评论中描述的方式，但不完全是。）

像这样：

Source1 from the toPeople和 1 from Peopleto的容量Jobs保证了一个人只会被选中做一项工作（因为他们总体上可以贡献的最大流量是 1）。但是，> 1从Jobs到的能力Terminal允许可以为该工作分配一个以上的人。

如果一个人还可以完成一项以上的工作，那么从Source到的最大流量会Person增加该数量：

其中i、j、k和x是具有值的整数的替代项>= 1

这里要记住的关键是左侧的流动能力People决定了他们可以从事多少工作，而右侧的流动能力Jobs决定了可以为多少人分配该工作。中间的容量不应该改变。