给定一个 (n) 个点 (m) 条边的无向图，求该图的最大匹配。
二分图最大匹配，一般用匈牙利算法完成，图中只存在偶环。
而一般图不能分为左右两部，存在奇环，如何处理奇环，是带花树算法的关键。
若将偶环缩为一点，则该图可以简化为只有奇环的无向图。
对于奇环内部，两两匹配后必定多出一个点不能匹配，则将该点与环外部的点相匹配即可。
通过类似匈牙利算法的多次增广，可以找到最大匹配。
点数为 (n)，边数为 (m) 。
时间复杂度： (O(n^2 m))
#include
using namespace std;
const int N = 1005;
int n, m, cnt;
int fa[N], vis[N], tag[N], pre[N], match[N];
queue q;
vector e;
vector G[N];
void addEdge(int a, int b, int i)
{
e.push_back(b);
e.push_back(a);
G[a].push_back(i);
G[b].push_back(i ^ 1);
}
inline int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline int lca(int x, int y)
{
++cnt;
while (true)
{
if (x)
{
x = find(x);
if (tag[x] == cnt) return x;
tag[x] = cnt;
x = pre[match[x]];
}
swap(x, y);
}
}
inline void blossom(int x, int y, int p)
{
while (find(x) != p)
{
pre[x] = y; y = match[x];
vis[y] = 1; q.push(y);
if (find(x) == x) fa[x] = p;
if (find(y) == y) fa[y] = p;
x = pre[y];
}
}
bool bfs(int s)
{
for (int i = 1; i
感谢支持！
Original: https://www.cnblogs.com/jjmg/p/13869334.html
Author: Chiron-zy
Title: 【模板】一般图最大匹配（带花树算法）/洛谷P6113
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583712/
转载文章受原作者版权保护。转载请注明原作者出处！