RainAir
My OI Blog
RainAir
二分图最大匹配

二分图定义

二分图是图论中的一种特殊模型,是图论中的一种特殊的模型。我们设$ G(V,E) $是一个无向图,如果顶点$ V $能被分割为两个互不相交的子集,并且图中的每条边$ (i,j) $所关联的两个顶点$ i $和$ j $分别属于这两个不同的顶点集,则称图$ G $为一个二分图。
我们要实现的是求二分图的最大匹配。

算法实现

首先从任意一个未被配对的点u开始,从点u的边中找出一条边开始配对(设这条边是u->v)。如果点v没有被配对,则配对成功,找到了一条增广路。如果点v已经被配对了,就要尝试去移动原来与v配对的点,如果成功,更新原来的配对关系,配对树加一。如果失败,换一条边。
我们用match记录配对关系,如果u与v配对,则计作 $ match[v] = u $和 $ match[u] = v $
重复上述步骤直到找不出新的增广路为止。

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/141
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

二分图最大匹配
二分图定义 二分图是图论中的一种特殊模型,是图论中的一种特殊的模型。我们设$ G(V,E) $是一个无向图,如果顶点$ V $能被分割为两个互不相交的子集,并且图中的每条边$ (i,j) $所关联的…
扫描二维码继续阅读
2018-01-07
标签
近期评论