这是一个比较神奇的算法,历史比较悠久,但好像并不是特别的热门。(#_#)
作用是用来求一般图的最大匹配,时间复杂度为 \(O(n^3)\) ,由于证明比较复杂,这里不给出。


它的思路跟匈牙利算法类似,也是按顺序为没有匹配的点寻找一条增广路。
所以以下部分是一样的:


由于是一般图,在搜索时可能出现一些环,所以在BFS时需要特别地考虑。
我们将奇环称之为花(・ิω・ิ)
若是出现偶环,则我们直接无视(●′ω`●);若是花,则我们要进行一系列操作(并查集)把它看做一个点。
我们将点分为两种,在一个匹配中先访问到的为第一种,后访问到的丢到队列中,为第二种。

以下是BFS的过程:

其中pre数组是为了在找到增广路后方便回溯的数组。


接下来就是缩花的过程,最难以理解,大家自行体会(´・ω・`)
首先找到两个点的LCA,这里可以使用暴力直接找。
然后把一路上的点通过并查集连到一块,并构成新的匹配。

(⊙⊙!)


然后就没有了(^_^)

下面是模板,UOJ上跑了120ms: