检查我们是否可以选择不同颜色的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

这是一个匹配问题.

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

使用标准算法在二分图中构建最大匹配.在福特Fulkerson算法将是很容易实现.但Hopcroft-Karp算法运行速度更快.