题解 P6113 【【模板】一般图最大匹配】

upd：修改了几处语病。 【模板】带花树算法 能使用匈牙利算法做出[这道题](https://www.luogu.com.cn/problem/P3386)会对理解本文有帮助。 定义图的一组匹配为图的一个边集，保证边集中的边两两没有公共定点。 定义一条边是匹配边当且仅当这条边属于一个匹配，一个点被匹配当且仅当这个点是一条匹配边的端点。 寻找图上的最大匹配常常使用增广路算法。在这里，一条增广路定义为一条起点和终点不相同且均未被匹配的路径，保证路径上的边是非匹配边和匹配边交替。 可以发现，增广路一定包含奇数条边，且将这些边依次翻转（即匹配边变成非匹配边，非匹配边变成匹配边）后得到的还是一组匹配。 这样，每找到一条增广路，就可以使得图中的匹配数量 +1。因此，一个匹配是最大匹配当且仅当图中不存在增广路。 对于二分图，可以使用匈牙利算法可以在 $O(nm)$ 的时间内求出最大匹配。 匈牙利算法寻找的增广路实际上是一条有向的增广路，其中的匹配边的方向是唯一的。这在二分图中是正确的，但是在一般图中，匹配边在增广路中的方向不是唯一的，这使得匈牙利算法中一个点不能被访问两次的限制错误。因此一般图的最大匹配不能用匈牙利算法求解。 一般图和二分图的区别只有奇环的有无，对于一个大小为 $2k+1$ 的奇环，最多只有 $k$ 对匹配，因此一定有至少一个节点能够向外匹配。同时，通过环内增广，每个节点都可以成为这个向外匹配的点。 因此，在求匹配的时候，一个奇环和一个节点是等价的，所以可以将奇环缩成点后当成二分图进行匹配。 将奇环缩成的节点叫做花，对原图用 bfs 找一条增广路，这棵节点可能是花的 bfs 树就称作带花树。 在带花树上 bfs，并尝试对访问到的节点进行黑白染色。假设起点是黑点，那么黑->白的边是非匹配边，白->黑的边是匹配边。遍历黑点的出边，如果访问到的点未被染色且未被匹配，那么就找到了一条增广路。如果被匹配了，则将该点染白色，将该点的匹配点染黑色并加入队列中。 如果访问到的点是白点，那么找到了一个偶环，没有影响无需处理。如果访问到的点是黑点，那么找到了一个奇环，在 bfs 树上找到这两个点的 lca 即可定位这个奇环，可以用并查集将其缩起来。因为缩起来的环是一个黑点，所以环上的白点都需改成黑点并加入到队列中。 为了方便地遍历这条增广路，对每个点存一个前驱 pre 表示这个点出发走一条非匹配边后应该到达哪个节点。被缩掉的环上的非匹配边的 pre 应该都是双向的，在缩环时处理一下。 可以发现，通过缩环减少一个点的复杂度为均摊 $O(logn)$，因为使用了并查集。找到一条增广路最坏情况下需要遍历整张图，复杂度为 $O(n+m)$。 因此，用带花树算法求出一般图最大匹配的复杂度为 $O(n(nlogn+m))$，通常可以当做 $O(nm)$（和匈牙利一样跑不满就是了）。 题外话，额外存一下每个花在树上的节点是哪一个就可以按秩合并了。 ```cpp #include<bits/stdc++.h> using namespace std; #define I inline int #define V inline void #define FOR(i,a,b) for(int i=a;i<=b;i++) #define REP(u) for(int i=h[u],v;v=e[i].t,i;i=e[i].n) const int N=1e3+1,M=1e5+1; queue<int>q; int n,m,tot,qwq,ans; int h[N],lk[N],tag[N],fa[N],pre[N],dfn[N]; struct edge{int t,n;}e[M]; V link(int x,int y){lk[x]=y,lk[y]=x;} V add_edge(int x,int y){ if(!lk[x]&&!lk[y])link(x,y),ans++; e[++tot]=(edge){y,h[x]},h[x]=tot; e[++tot]=(edge){x,h[y]},h[y]=tot; } V rev(int x){if(x)rev(x[pre][lk]),link(x,pre[x]);} I find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} I lca(int x,int y){ for(qwq++;;x=x[lk][pre],swap(x,y)) if(dfn[x=find(x)]==qwq)return x; else if(x)dfn[x]=qwq; } V shrink(int x,int y,int p){ for(;find(x)!=p;x=pre[y]){ pre[x]=y,y=lk[x],fa[x]=fa[y]=p; if(tag[y]==2)tag[y]=1,q.push(y); } } I blossom(int u){ FOR(i,1,n)tag[i]=pre[i]=0,fa[i]=i; tag[u]=1,q=queue<int>(),q.push(u); for(int p;!q.empty();q.pop())REP(u=q.front()) if(tag[v]==1) p=lca(u,v),shrink(u,v,p),shrink(v,u,p); else if(!tag[v]){ pre[v]=u,tag[v]=2; if(!lk[v])return rev(v),1; else tag[lk[v]]=1,q.push(lk[v]); } return 0; } int main(){ scanf("%d%d",&n,&m); for(int x,y;m--;add_edge(x,y))scanf("%d%d",&x,&y); FOR(i,1,n)ans+=!lk[i]&&blossom(i); cout<<ans<<'\n'; FOR(i,1,n)cout<<lk[i]<<' '; return 0; } ```