给定两个集合，存在一些连接两个集合的边表示配合，来自不同集合的一对元素构成一个配对，求最大的配对数量。

集合内无边，所以构成二分图，求二分图的最大匹配。

图的匹配：任意两条边都没有公共端点的边的集合被称为图的一组匹配。

二分图最大匹配：在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

如果二分图中存在一条连接两个非匹配点的路径 ，使得非匹配边与匹配边在路径上交替出现，那么称该路径是匹配 \(S\) 的增广路（也称交错路）。

奇数边是非匹配边，偶数边是匹配边。

重复第 2 步，直至图中不存在增广路。

双标记对于访问二分图里所有点得到的匹配是实际值，单标记访问所有点得到的匹配是2倍，如果访问一个集合点则是实际值，单标记更多用于两集和已被分隔开的情况。

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！