algorithm - 使用最大流量，更难的版本将工作分配给人员

Question

我正在自学最大流量，但出现了这个问题：

原来的问题是

• 假设我们有一个工作列表

  {J1，J1，...，Jm}

• 以及已申请的人员名单

  {P1, P2, P3,...,Pn}

• 每个人都有不同的兴趣，其中一些人申请了多个工作（每个人都有一份他们可以做的工作清单）

• 任何人不得从事超过 3 份工作。

所以，这个问题可以通过在下图中找到最大流量来解决

我理解这个解决方案，但是

问题的更难版本

如果加上这些条件呢？

• 简单版的前 3 个条件（工作和人员列表，每个人都有兴趣或能力列表）仍然相同

• 该公司仅雇用 Vi 人员担任 Ji

• 公司希望雇用尽可能多的人

• 一个人可以从事的工作数量没有限制。

我应该在图中做出什么改变，以便我的解决方案也能满足这些条件？或者如果我需要不同的方法，请告诉我。

在任何人说话之前，这不是功课。这只是自学，但我正在研究最大流量，问题出在那个区域，所以解决方案应该使用最大流量。

Answer 1

• 对于一个工作的多人：

  从Ji到的边t将具有与该工作的人数相等的容量。J1例如，如果工作#1 可以有三个人，这意味着从到边缘的容量为三个t。

• 对于雇用尽可能多的人的要求：

  我认为这不可能通过单个流程图实现。这是一个如何完成的算法：

  1. 运行一次流算法。
  2. 对于每个人：
     1. 尝试将输入容量降低到低于当前流量的 1。
     2. 再次运行流算法。
     3. 虽然这不会减少总流量，但从 (2.1.) 开始重复。
     4. 容量加一，恢复最大流量。
  3. 直到没有人被添加，从 (2.) 开始重复。
      

• 对于不限制工作数量：

  从s到的边Pi将具有等于该人的适用工作数量的最大流量。