java - Ford Fulkerson 算法 Java

Question

我需要帮助实现以下调度问题的高效算法。

明天有n位患者来医院体检，但只有2位医生(A医生和B医生)。每次体检占用医生1个时间段。如果可能，我需要仅使用 1 名医生将那些 n 患者分配到 n 时间段。如果不可能有 1 名医生，我最多可以分配 2 名医生，因为只有 2 名医生可用。如果2个医生还是不够。简单的输出impossible

我将患者的可用性作为输入。比如有5个病人，病人1只在1、2、5时段可用，病人2在3、4时段可用，病人3在1时段可用……以此类推.

P1: 1 2 5
P2: 3 4
P3: 1
P4: 2
P5: 3 5

在这种情况下，我只需要一名医生来完成这项工作。输出

P1: Time slot 5 - Doc A
P2: Time slot 4 - Doc A
P3: Time slot 1 - Doc A
P4: Time slot 2 - Doc A
P5: Time slot 3 - Doc A

如果我得到这样的输入:

P1: 1 2 5
P2: 3 4
P3: 2
P4: 2
P5: 3 5

然后我需要指定两位医生，因为 P3 和 P4 的可用性存在冲突。输出:

P1: Time slot 5 - Doc A
P2: Time slot 4 - Doc A
P3: Time slot 2 - Doc A
P4: Time slot 2 - Doc B
P5: Time slot 3 - Doc A

解决此类问题的最有效算法是什么？我如何为此实现 Ford Fulkerson 算法？

到目前为止我做了什么。

我试图将每个患者的可用时间段存储到单独的数组中。

按长度对数组进行排序。首先为患者分配可用时间最少的患者。

分配患者后，删除其余数组中的此时间段，并再次按长度对数组进行排序。

重复此过程，直到分配完所有患者。

Answer 1

让我们更深入地了解这个问题。我们有一组患者，一组时间段以及它们之间的一些联系(给定时间患者的可用性)。它看起来就像二分图中的最大匹配问题!所以第一组顶点应该对应于患者(每个患者一个顶点)，第二组应该对应于时隙(每个时隙一个顶点)。当且仅当患者在这个时隙可用时，第一组顶点和第二组顶点之间存在一条边。如果最大匹配大小等于患者数量，那么一个医生就足够了，否则就不行。

2位医生如何解决这个问题？几乎一样的方式。我们仍然可以为患者和时间段构建二分图，但现在我们在每个时间段的第二组中有 2 个顶点(一个用于第一个医生，第二个用于另一个医生)。边缘也以相同的方式添加。同样，我们需要检查的是最大匹配大小是否等于患者数量。

要在二部图中找到最大匹配，可以使用 Dinic 或 Hopcroft-Karp 算法来获得 O(M * sqrt(N)) 时间复杂度，其中 N 是顶点数，M 是边数。