问带顶点度约束的加权二部匹配

EN

我遇到了一个问题，我可以将其概念化如下：

我们有一组人。M子集代表着他们的种族，如白人、西班牙裔、亚洲人等等。如果这些人的任何组合，我想看看他们是否是一个多元化的群体。

一个多样化的群体是一个满足多个要求的群体，每个要求都是“至少属于子集Si的群体中的Ki人”的形式。这里有一个棘手的部分，一个人只能用来满足一个需求。正如所述，您不能将他/她用于多种需求。

举个例子：

给予：

至少有两人来自Hispanic= {a，b，c}

至少有两人来自Asian={a，d，e}

组{a，c，d}是一个多样化的组吗？

组{a，c，d}并不不同，因为您不能将a计算为西班牙裔和亚洲人。但是，群{a，c，d，e，f}是不同的，因为我们有两个拉丁裔a和c，以及两个亚洲d和e。

企图：

这是赋值问题的一个实例。这些工作是种族的，我们可以根据需要把多少民族的人都放进去。例如，如果我们需要两名西班牙裔人，那么我们就提供两份西班牙裔工作。然而，只有一些人能够做一项特定的工作。

这是我迄今为止的尝试：

我将构造一个二分图，一方面是人的集合，，P，，另一方面是，S，的种族集合。如果他/她属于种族，我们将在p_i和民族S_i之间设置一个边缘。现在，我们将修改该图，对于每个民族S_i复制它的k_i times ( S_{i，1}，S_{i,2}，.，S_{i，k_i})。并相应地添加新的边。找出这个图的最大匹配M。

现在，将S_{i，j}合并到一个S_i中，您就有了一个不同的组。然而，最大匹配只是解决这个问题的一个可能的解决方案。我的问题是一个决策问题，我想检查一个给定的组是否是一个解决方案。