我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm并且无法理解。似乎这个例子是在假设每个工作只能接受 1 人并且每个人想要一份工作的情况下。我想知道如果 v 集的容量 > 1(可以为该工作雇用多个人)和 u 集 > 1(每个人想要超过 1 个工作),算法/代码将如何变化?
问问题
5029 次
1 回答
9
要允许为工作分配多个人,您只需将边缘容量从 修改Jobs
为Terminal
(类似于 Niklas B. 在他的评论中描述的方式,但不完全是。)
像这样:
Source
1 from the toPeople
和 1 from People
to的容量Jobs
保证了一个人只会被选中做一项工作(因为他们总体上可以贡献的最大流量是 1)。但是,> 1
从Jobs
到的能力Terminal
允许可以为该工作分配一个以上的人。
如果一个人还可以完成一项以上的工作,那么从Source
到的最大流量会Person
增加该数量:
其中i
、j
、k
和x
是具有值的整数的替代项>= 1
这里要记住的关键是左侧的流动能力People
决定了他们可以从事多少工作,而右侧的流动能力Jobs
决定了可以为多少人分配该工作。中间的容量不应该改变。
于 2014-04-01T07:53:44.557 回答