二分匹配

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带有定向边缘的单个节点添加S到M(这是您的"超级源"节点)中的每个节点.

3. 添加一个节点T从每个节点有向边F来T(这是你的"超汇"节点).

4. 现在,你需要找到的最大流量(体重1的所有边缘)从S到T.

那么最大的流量到底是什么？来自to 的流是一组边,使得对于每个节点(除了和),其磁通边缘的权重与其磁通边缘的权重相同.想象一下,你的图表是一系列管道,你正在系统中注入水并将其放出.在它们之间的每个节点,进入的水量必须与出水量相同.STSTST

尝试说服自己,流程对应于原始集合的匹配.(给定流程,如何获得匹配？给定匹配,如何获得流量？)

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