c - 二部图中的最大匹配

Question

我在二分图问题中陷入了最大匹配问题。问题是这样的:

给定一 block 有 m 个圆孔的板和一组 n 个圆盘。孔的编号为 h₁, ..., h_m，圆盘的编号为 d₁, ..., d_n .

我们有一个 m 行 n 列的矩阵 A。如果 h_i 可以拟合 d_j(即 h_i 的直径 ≥ d _{的直径，则 A[i][j] = 1 >j})，否则为 0。

考虑到任何孔最多可以包含一个圆盘，我需要找到孔圆盘拟合最大的配置。

我读到这个问题可以建模为网络流问题，但无法准确理解如何建模。有人可以解释如何做到这一点吗？另外，有没有相关的 C 代码可供我查看？

Answer 1

从二分匹配到最大流量的减少实际上是相当漂亮的。当给定二部图时，您可以将该图视为两列节点，通过从第一列到第二列的边连接:

  A ----- 1
  B --\   2
  C    \- 3
 ...     ...
  Z       n

为了将问题减少到最大流，您首先将所有边缘从第一列引导到第二列，以便流只能从左列移动到右列。执行此操作后，您将引入两个新节点 s 和 t，它们分别充当源节点和终端节点。您定位 s，使其连接到左侧的所有节点，定位 t，使其连接到右侧的每个节点。例如:

     A ----- 1
 /   B --\   2   \
s-   C    \- 3   - t
 \  ...     ...  /
     Z       n

这里的想法是，从 s 到 t 的任何路径都必须进入左列中的节点之一，然后穿过某些边到达右列，然后从那里到达 t。因此，从匹配中的边到 s-t 路径有一个简单的一对一映射:只需从 s 到边的源，然后沿着边走，然后沿着从端点到节点的边走t。此时，我们的目标是找到最大化从 s 到 t 的节点不相交路径数量的方法。我们可以使用最大流量来实现这一点，如下所示。首先，将离开 s 的每条边的容量设置为 1。这确保最多有一个单位的流量进入第一列中的每个节点。类似地，将穿过两列的每条边的容量设置为 1，这样我们要么选择该边，要么不选择该边，而不是可能以某种多重性来选择它。最后，将离开第二列进入 t 的边的容量也设置为 1。这确保了右侧的每个节点仅匹配一次，因为我们无法将超过一个单位的流量推过它。

构建流量网络后，使用任何标准算法计算最大流量。 <强> Ford-Fulkerson 是一个在这里表现良好的简单算法，因为图中的最大流量等于节点数。它的最坏情况性能为 O(mn)。或者，高度优化的 Hopcroft-Karp algorithm 可以在 O(m√n) 时间内完成此操作，这会更好。

对于 C 实现，在 Google 上快速搜索 Ford-Fulkerson 步骤就会出现 this link 。您需要先构建流网络，然后再将其传递到此代码中，但构建并不太复杂，我认为您应该不会遇到太多麻烦。

希望这有帮助!