Hopcroft-Karp算法在现实调度问题中的实现

Question

我们有一个最大二部匹配问题，使得M个人需要被分配N个时隙，使得每个时隙至少有一个人，M个人的一个子集将在这N个时隙中各有一个，而其他人将有2个时隙分配给他们。你知道吗

例如：8个吃角子老虎机，6个人。这些人中的4人将只需要覆盖每个插槽1，但其他2人将覆盖每个插槽2。因此，将分配所有8个插槽（4*1+2*2）。你知道吗

输入数据将反映M个人中的哪一个将覆盖每个1个插槽，哪一个将覆盖每个2个插槽。你知道吗

到目前为止，我们使用HopCroft Carp实现了以下功能：

from hopcroftkarp import HopcroftKarp
graph = {'john': {12, 3, 5}, 'june': {5, 10, 8}, 'joe': {5, 3}}
HopcroftKarp(graph).maximum_matching(keys_only=True)
>> {'joe': 3, 'june': 5, 'john': 12}

为了使问题更加复杂，每个用户都可以指出3个选项中的一个：preferred、not preferred but available和conflict (not available)。你知道吗

我们如何为人们分配槽位，使大多数人得到首选槽位，然后是“首选但不可用槽位”，没有人得到“不可用”槽位？我们如何调整我们现有的信息上面考虑到这三个选择，人们有？另外，我们如何进一步反映一些人需要分配2个位置？你知道吗

我们已经研究了similar questions，但是它们只为人们available或not available提供了两种选择。你知道吗