偶匹配 [英] Bipartite Matching

问题描述

我如何实现一个双向匹配算法（可能是基于一个最大流算法）的C或C ++？

How can I implement a bipartite matching algorithm (probably based on a max-flow algorithm) in C or C++ ?

要具体，我有这样的投入在一个文件中： （1,3） （1,5） （2,5）

To be specific, I have this input in a file: (1,3) (1,5) (2,5)

（M，F） - >其中男性和F M RE presents id是女的ID

(M,F) --> where M represents id of MALE and F is id of FEMALE.

我需要找到比赛和表演相匹配夫妇的最大数量。 喜欢： 符合条件：1和3，2和5

I need to find the maximum number of matches and show matched couples. Like: matches: 1&3 , 2&5

我读过的一些书，我可以对算法在网络最大流基地这个问题，但我无法找到比这句话以外的任何具体信息这个问题可以通过....算法来解决。 我对最大流的小知识，不知道如何实现它要么...

I have read in some books I can base this problem on a "maximum flow in a network" algorithm, but I couldn't find any specific info other than the sentence "this problem can be solved by .... algorithm". I have little knowledge about max-flow, and dont know how to implement it either...

推荐答案

是的，偶匹配可降低到最大流量：

Yes, bipartite matching can be reduced to maximum flow:

1. 您是节点定套 M 和 F 。从节点 M 在 M 添加有向边到节点 F 在 F 如果你有一对（M，F）在您的文件。

1. You're given sets of nodes M and F. Add a directed edge from a node m in M to a node f in F if you've got the pair (m, f) in your file.

从取值添加一个节点取值有向边的每一个节点 M （这是你的超级源节点）。

Add a single node S with a directed edge from S to every node in M (this is your "super-source" node).

添加一个节点 T 从每个节点 F 来有向边 T （这是你的超汇节点）。

Add a single node T with a directed edge from every node in F to T (this is your "super-sink" node).

现在，你需要找到从取值的最大流量（体重1你的所有边），以 T 。

Now, you need to find the maximum flow (with all your edges of weight 1) from S to T.

那么到底是什么最大流量？ A 流的距离取值到 T 是一组边，使得每个节点（除了取值和 T ），它的的通量的边缘的权重是一样的作为它的超出流量的边缘的权重。试想一下，你的图是一个系列的管道，而你的取值浇水系统，让它在 T 。在之间的每一个节点，水会在的量必须是相同的水的量出来。

So what the heck is maximum flow? A flow from S to T is a set of edges such that for each node (except S and T), the weight of its in-flux edges is the same as the weight of its out-flux edges. Imagine that your graph is a series of pipes, and you're pouring water in the system at S and letting it out at T. At every node in between, the amount of water going in has to be the same as the amount of water coming out.

试着说服自己，流量相当于原来的设置相匹配。 （给定一个流程，怎么给你弄一个匹配？给定一个匹配，怎么给你得到一个流？）

Try to convince yourself that a flow corresponds to a matching of your original sets. (Given a flow, how to you get a matching? Given a matching, how to you get a flow?)

最后，找到图中的最大流量，您可以使用福特Fulkerson算法 。上面的维基百科页面给出了它的一个很好的说明，与伪code。

Finally, to find the maximum flow in a graph, you can use the Ford-Fulkerson algorithm. The above wikipedia page gives a good description of it, with pseudo-code.

这篇关于偶匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！