在二分图中的最大匹配

Question

我在二分图问题中遇到最大匹配。问题是这样的：

给定一个有m个圆孔的板，并给出一组n个圆盘。孔编号为h ，...，h _m，以及作为d的圆盘，...，d _n。

我们有一个m行n列的矩阵A. A [i] [j] = 1如果h _我可以适合d _Ĵ（即，h的_我 ≥直径d _Ĵ的直径），否则为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必须进入在左侧栏中的一个节点，然后过一些边缘到右列，并从那里吨。因此，从匹配中的边缘到st路径有一个简单的一对一映射：只需从s到边缘源的路径，然后沿着边缘，然后沿着边缘从端点到节点吨。在这一点上，我们的目标是找到最大化从s到t的节点不相交路径的数量的方式。我们可以按如下方式使用最大流量完成此操作。首先，将每个边缘的容量设置为1.这确保了最多一个流量单位进入第一列中的每个节点。类似地，将每个穿过两列的边的容量设置为1，这样我们可以选择边或者不选，而不是采用多重选择。最后，将离开第二列的边的容量设置为t也是一样。这确保了右侧的每个节点只匹配一次，因为我们不能推动超过一个单位的流量。

一旦你构建了流网络，使用任何标准算法计算最大流量。 Ford-Fulkerson是一个简单的算法，在这里表现良好，因为图中的最大流量等于节点数量。它具有O（mn）的最差情况表现。或者，高度优化的可以在O（m √ n）时间内做到这一点，这可以更好。

至于C的实施，快速谷歌搜索Ford-Fulkerson步骤出现了this link。在将代码传递给代码之前，您需要构建流程网络，但是构建并不太复杂，我认为您不应该遇到太多麻烦。

希望这会有所帮助！