c++ - 二分匹配

Question

如何在 C 或 C++ 中实现二分匹配算法(可能基于最大流算法)？

具体来说，我在一个文件中有这个输入:(1,3)(1,5)(2,5)

(M,F) --> 其中 M 代表 MALE 的 id，F 是 FEMALE 的 id。

我需要找到最大匹配数并显示匹配的情侣。喜欢:匹配:1&3 , 2&5

我在一些书中读到我可以将这个问题基于“网络中的最大流量”算法，但是除了“这个问题可以通过......算法解决”这句话之外我找不到任何具体信息”。我对max-flow知之甚少，也不知道如何实现...

Answer 1

是的，二分匹配可以减少到最大流:

1. 给定了节点集 M 和 F。添加一条从M中的节点m到F中的节点f的有向边在你的文件中对(m, f)。

2. 将一个节点 S 添加到 M 中的每个节点(这是您的“ super -源”节点)。

3. 添加一个节点 T，它有从 F 中的每个节点到 T 的有向边(这是你的“ super -汇”节点)。

4. 现在，您需要找到从 S 到 T 的最大流量(所有边的权重都为 1)。

那么什么是最大流量呢？从 S 到 T 的 flow 是一组边，这样对于每个节点(除了 S 和 T)，它的 in-flux 边的权重与它的 out-flux 边的权重相同。假设您的图形是一系列管道，您在 S 处向系统中注水，并在 T 处放水。在中间的每个节点，流入的水量必须与流出的水量相同。

尝试说服自己流对应于原始集的匹配。 (给定一个流，你如何得到一个匹配？给定一个匹配，你如何得到一个流？)

最后，要找到图中的最大流量，您可以使用 Ford-Fulkerson algorithm .上面的维基百科页面用伪代码给出了很好的描述。