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

Question

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

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

例：

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

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

在这里你不能从这些盒子中选择4个颜色A，B，C，D的球。条件是你可以从每个盒子里只挑一个球。

Answer 1

这是一个匹配问题。

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

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