从两组中各取一个元素
Picking one element from each of the two sets
我们有一群人，说 P1、P2、P3、P4。我们有两套。假设一组是 {1, 2, 3, 4}，另一组是 {A, B, C}。每个人都有一个元素列表，他可以从两个集合中的每一个中选择。当一个人拥有两个集合中的两个元素时，我们说这个人准备好了。我们希望最大限度地增加准备人员的数量。同一元素不能使用两次。像下面的例子：
People: P1, P2, P3, P4
Set1: {1, 2, 3, 4}
Set2: {A, B, C}
P1 can pick from {1, 2} and {B, C}
P2 can pick from {1, 2, 3} and {C}
P3 can pick from {1, 2} and {B, C}
P4 can pick from {1} and {A, B, C}
上述示例的一个可能解决方案是：
P1 picks none
P2 picks 3 and C
P3 picks 2 and B
P4 picks 1 and A
想过对每个集合分别使用贪心，但实际上要得到最优解，一个集合的解有时不得不对另一集合做出妥协。
编辑：
最大流解决方案解决了原始问题。现在如果每个人在 {1, 2, 3, 4} 中选择时都有自己的偏好怎么办？例如，P1 比 1 更喜欢 2。当 P1 可以选择 1 或 2 时，他总是会选择 2。
这可以通过计算如下构造的流网络上的最大流来解决：
- 构建源节点
Source
- 为第一组
#1到#4的元素构造一个节点；将每个节点连接到 Source.
- 为每个人构建一个节点。根据他们的兼容性列表将每个人连接到 noodes
#1..#4（即 P1 连接到 #1 和 #2，P2 #1、#2 和 #3，等等）
- 为第二组的每个元素构造一个节点
A..C。根据兼容性列表将每个节点连接到个人节点。
- 构造一个节点
Drain，并将每个节点从A..C连接到排水管。
所有边和所有顶点的容量均为 1。这是基于您的兼容性列表的示例：
现在 运行 此图定义的流量网络中的 several max flow algorithms 之一。您获得的最大流量提供了最佳分配：
我们有一群人，说 P1、P2、P3、P4。我们有两套。假设一组是 {1, 2, 3, 4}，另一组是 {A, B, C}。每个人都有一个元素列表，他可以从两个集合中的每一个中选择。当一个人拥有两个集合中的两个元素时，我们说这个人准备好了。我们希望最大限度地增加准备人员的数量。同一元素不能使用两次。像下面的例子：
People: P1, P2, P3, P4
Set1: {1, 2, 3, 4}
Set2: {A, B, C}
P1 can pick from {1, 2} and {B, C}
P2 can pick from {1, 2, 3} and {C}
P3 can pick from {1, 2} and {B, C}
P4 can pick from {1} and {A, B, C}
上述示例的一个可能解决方案是：
P1 picks none
P2 picks 3 and C
P3 picks 2 and B
P4 picks 1 and A
想过对每个集合分别使用贪心，但实际上要得到最优解，一个集合的解有时不得不对另一集合做出妥协。
编辑：
最大流解决方案解决了原始问题。现在如果每个人在 {1, 2, 3, 4} 中选择时都有自己的偏好怎么办？例如，P1 比 1 更喜欢 2。当 P1 可以选择 1 或 2 时，他总是会选择 2。
这可以通过计算如下构造的流网络上的最大流来解决：
- 构建源节点
Source - 为第一组
#1到#4的元素构造一个节点；将每个节点连接到Source. - 为每个人构建一个节点。根据他们的兼容性列表将每个人连接到 noodes
#1..#4（即P1连接到#1和#2，P2#1、#2和#3，等等） - 为第二组的每个元素构造一个节点
A..C。根据兼容性列表将每个节点连接到个人节点。 - 构造一个节点
Drain，并将每个节点从A..C连接到排水管。
所有边和所有顶点的容量均为 1。这是基于您的兼容性列表的示例：
现在 运行 此图定义的流量网络中的 several max flow algorithms 之一。您获得的最大流量提供了最佳分配：