13

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

4

1 回答 1

9

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

像这样:

流网络

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

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

另一个流网络

其中ijkx是具有值的整数的替代项>= 1

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

于 2014-04-01T07:53:44.557 回答