分配作业使用最大流量的人，很难版 [英] Assigning jobs to people using Maximum Flow, harder version

问题描述

我的自我学习的最大流量，有这个问题：

原来的问题是

• 假设我们有作业列表

  {J1，J1，...，JM}

• 和已申请了他们的人的名单

  {P1，P2，P3，...，PN}

• 每个人有不同的利益，其中有些已经申请了多个作业（每个人都有工作，他们可以做一个列表）

• 没有人被允许做3个以上的就业机会。

所以，这个问题可以通过寻找在下面的图中的一个最大流量解决

我理解这个解决方案，但

问题的较硬版本

如果这些条件都加进去呢？

• 的轻松版的前3个条件（就业和个人，每个人名单有兴趣或能力的列表）仍保持不变

• 在compony是采用只六作业吉

人员

• 在compony想雇用尽可能多的人尽可能

• 有对的人也无法完成工作的数量没有限制。

我应该做的图有什么区别，使我的解决方案能够满足这些条件呢？或者，如果我需要一个不同的方法，请告诉我。

在任何人说什么，这不是功课。这只是自学，但我学习最大流量，问题是在这方面因此该解决方案应该用最大流量。

解决方案

• 对于多人为一个作业：

  从冀到 T 边缘都享有平等的人该作业数量的能力。例如。如果作业＃1可以有三个人，这相当于一个容量三的边缘​​从 J1 到 T 。

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

  我不认为这是可能的一个流图。这是一种算法，它是如何的可以的完成：

  1. 运行流算法一次。
  2. 对于每个人：
     1. 尝试对进来的能力降低一个低于目前流量。
     2. 重新运行流算法。
     3. 虽然这并不降低总流量，从重复（2.1）。
     4. 在增加容量的，恢复的最大流量。
  3. 在此之前没有更多的人被添加，由式（2）重复。
     ＆NBSP;

• 有关的就业岗位数量没有限制：

  从边缘小号到丕将有一个最大流量等于适用的作业数量的那个人。

I am self studying max flow and there was this problem:

the original problem is

• Suppose we have a list of jobs

  {J1, J1,..., Jm}

• and a list of people that have applied for them

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

• each person have different interests and some of them have applied for multiple jobs (each person has a list of jobs they can do)

• nobody is allowed to do more than 3 jobs.

so, this problem can be solved by finding a maximum flow in the graph below

I understand this solution, but

the harder version of the problem

what if these conditions are added?

• the first 3 conditions of the easy version (lists of jobs and persons and each person has a list of interests or abilities) are still the same

• the compony is employing only Vi persons for job Ji

• the compony wants to employ as many people as possible

• there is no limitations for the number of jobs a person is allowed to do.

What difference should I make in the graph so that my solution can satisfy those conditions as well?or if I need a different approach please tell me.

before anyone say anything, this is not homework. It's just self study, but I am studying Maximum flow and the problem was in that area so the solution should use Maximum flow.

解决方案

• For multiple persons for a single job:

  The edge from Ji to t will have the capacity equal to the number of people for that job. E.g. If job #1 can have three people, this translates to a capacity of three for the edge from J1 to t.

• For the requirement of hiring as many people as possible:

  I don't think this is possible with a single flow-graph. Here is an algorithm for how it could be done:

  1. Run the flow-algorithm once.
  2. For each person:
     1. Try to decrease the incoming capacity to one below the current flow-rate.
     2. Run the flow-algorithm again.
     3. While this does not decrease the total flow, repeat from (2.1.).
     4. Increase the capacity by one, to restore the maximum flow.

  3. Until no further persons gets added, repeat from (2.).
      

• For no limitation on number of jobs:

  The edges from s to Pi will have a maximum flow equal the number of applicable jobs for that person.

这篇关于分配作业使用最大流量的人，很难版的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！