检查我们是否可以挑选 k 个不同颜色的球的算法

Question

我们有 n 个盒子和 k 个不同颜色的球。每个容器里有几个球。我们最多可以从每个盒子中选择一个球。

我们可以收集 k 个不同颜色的球吗？注意:每个容器最多有一个颜色的球。

示例:

假设我们有 5 个容器和 4 种不同的颜色 A,B,C,D

Box1 - A, D
Box2 - C,B
Box3 - D, A
Box4 - D
Box5 - D

这里你不能从这些盒子里选出颜色为A、B、C、D的4个球。条件是你只能从每个盒子里选一个球。

Answer 1

这是一个匹配问题。

从一个二分图开始，它的顶点是球和盒子的颜色，它的边是关系“这个球在那个盒子里”。你想构造一个最大匹配。如果最大匹配包括球的每种颜色，那么你的答案是肯定的，否则不是。

使用标准算法在二部图中构造最大匹配。 Ford–Fulkerson algorithm将很容易实现。但是 Hopcroft–Karp algorithm会跑得更快。