首页 > 分享 > 一般图最大匹配：带花树入门详解

一般图最大匹配：带花树入门详解

花匠小妙招
2024-11-27 09:50

前言

早就听说带花树这个算法，然而因为它用得并不多，所以一直没有去学。

今天闲得无聊，便来研究研究这个东西。

带花树简介

带花树，用于求一般图最大匹配。

与二分图不一样，一般图中最大的问题就是可能存在奇环。

而带花树和匈牙利算法（强烈建议在学习此算法之前先去学学匈牙利）之间主要不同其实也就两点：

匈牙利算法实现是dfs" role="presentation">dfs，带花树的实现是bfs" role="presentation">bfs。带花树在匈牙利算法的基础上增加了对奇环的处理。

接下来，就让我们具体了解带花树。

核心操作：奇环缩点（开花）

匹配是无向的，但我们可以人为给一个匹配中两点分别染上黑白两色，然后强制边从黑点连向白点。

则考虑对于一个奇环，假设它长度为2k+1" role="presentation">2k+1，那么我们可以令它自己形成k" role="presentation">k对匹配，并由剩下一个点对外匹配（注意，由于这是一个环，无论其中哪个点对外匹配，剩下的点都必然可以形成k" role="presentation">k对匹配）。

因此，我们完全可以把一个奇环缩成一个黑点（该点称为“花”），其中所有点都看作黑点。显然与原图是等价的。

具体的实现在后面有更详细的介绍，这里只是先为之后的叙述作一个简单铺垫。

bfs" role="presentation">bfs分类讨论

每次我们从bfs" role="presentation">bfs的队列中取出队首k" role="presentation">k（k" role="presentation">k必须是黑点），从它出发进行匹配，则相邻点v" role="presentation">v无非有下列几种情况：

v" role="presentation">v与k" role="presentation">k在一朵花中，或v" role="presentation">v是一个已经在此次bfs" role="presentation">bfs中访问过的白点，显然无需继续操作，直接跳过。 v" role="presentation">v是一个没有匹配过的点，那么v" role="presentation">v就可以与k" role="presentation">k匹配，返回true" role="presentation">true。 v" role="presentation">v是一个白点，则与匈牙利算法类似，我们尝试去给v" role="presentation">v的匹配点找一个新的匹配。 v" role="presentation">v是一个黑点，此时就说明出现了奇环，需要缩点。

其中，给v" role="presentation">v的匹配点找新匹配，只需要把v" role="presentation">v的匹配点加入队列即可。

而接下来我们依次解决如何进行找到匹配后的操作以及如何缩点。

1" role="presentation">1：找到匹配

考虑我们是从一个黑点出发，每次找到一个白点，然后去为白点的匹配点（黑点）搜索新的匹配。也就是说，bfs" role="presentation">bfs的路径必然长成这个样子：

黑-白=黑-白=黑-...-白=黑

其中，a-b表示b是从a搜到的（定义lstx" role="presentation">lstx为bfs" role="presentation">bfs中x" role="presentation">x的前继状态，则lstb=a" role="presentation">lstb=a），a=b表示a和b原本相互匹配（定义sx" role="presentation">sx为与x" role="presentation">x匹配的点，则sa=b,sb=a" role="presentation">sa=b,sb=a）。

也就是说，每个白点x" role="presentation">x前面的黑点可以表示为lstx" role="presentation">lstx，每个黑点x" role="presentation">x前面的白点可以表示为sx" role="presentation">sx。

现在如果为最后一个黑点找到了一个新的白点作为匹配，那么这条路径上的匹配关系就将被修改为：

黑=白-黑=白-黑=...=白-黑=白

则我们只要从这个新的白点开始，每次修改匹配关系，并往上跳到前一个白点即可。

至于如何找到前一个白点，设当前白点为x" role="presentation">x，则前一个黑点为lstx" role="presentation">lstx，那么前一个白点就是slstx" role="presentation">slstx。

2" role="presentation">2：缩点

实际上，此处缩点我们并不需要真的去缩点，只要开个并查集记录即可。

由于每次缩点的对象是两个黑点间的一条路径，因此我们需要找到两个点的LCA" role="presentation">LCA。

可以直接暴力，两个黑点轮流往上跳（每次跳到前一个黑点，即从x" role="presentation">x到lstsx" role="presentation">lstsx），边跳边打标记，第一次跳到的被打过标记的点就是LCA" role="presentation">LCA。

而缩点的过程也是类似往上跳并在并查集中修改的过程，就是要注意两点：

对于所有原先的白点，由于缩点将奇环中的全部点看作黑点，因此要加入bfs" role="presentation">bfs的队列中进行扩展。方便起见，我们把除LCA" role="presentation">LCA之外的lst" role="presentation">lst都改为双向的。

具体实现可以详见代码。

代码

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 1000 #define M 50000 #define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y) using namespace std; int n,m,ee,lnk[N+5];struct edge {int to,nxt;}e[2*M+5]; class FlowerMatchTree//带花树 {private:int s[N+5],lst[N+5],col[N+5],vis[N+5];queue<int> q;int f[N+5];I int fa(CI x) {return f[x]?f[x]=fa(f[x]):x;}//并查集I int LCA(RI x,RI y)//暴力跳LCA{static int ti=0;++ti,x=fa(x),y=fa(y);//ti为时间戳W(vis[x]^ti) vis[x]=ti,x=fa(lst[s[x]]),y&&(x^=y^=x^=y);return x;//边跳边打标记，注意跳到0之后不再跳}I void Blossom(RI x,RI y,CI p)//奇环缩点（开花）{W(fa(x)^p) lst[x]=y,y=s[x],!f[x]&&(f[x]=p),//并查集中合并!f[y]&&(f[y]=p),col[y]==2&&(col[y]=1,q.push(y),0),x=lst[y];//白点加入队列}I bool Match(CI x)//为x找个匹配对象{RI i;for(i=1;i<=n;++i) lst[i]=col[i]=f[i]=0;W(!q.empty()) q.pop();//每次bfs前清空RI k,p;q.push(x),col[x]=1;W(!q.empty()) for(i=lnk[k=q.front()],q.pop();i;i=e[i].nxt)//BFS{if(fa(k)==fa(e[i].to)||col[e[i].to]==2) continue;//若无需操作则跳过if(!col[e[i].to])//若没有访问过{if(col[e[i].to]=2,lst[e[i].to]=k,!s[e[i].to])//如果是一个没匹配过的点{for(k=e[i].to;k;k=p) p=s[lst[k]],s[k]=lst[k],s[lst[k]]=k;return 1;}//回跳并修改col[s[e[i].to]]=1,q.push(s[e[i].to]);continue;//把匹配点加入队列}p=LCA(k,e[i].to),Blossom(k,e[i].to,p),Blossom(e[i].to,k,p);//缩点}return 0;}public:I void Solve(){RI i,t=0;for(i=1;i<=n;++i) !s[i]&&Match(i)&&++t;//枚举点，若尚未匹配则去求匹配for(printf("%dn",t),i=1;i<=n;++i) printf("%d%c",s[i]," n"[i==n]);//输出答案} }T; int main() {RI i,x,y;for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);return T.Solve(),0; }