【概述】

带花树算法用于解决一般图的最大匹配问题。

对于一个图 G(V,E)，他的匹配 M 是二元组 (u,v) 组成的集合，其中 u,v∈V,(u,b)∈E，且 M 中不存在重复的点，当 |M| 最大的时候，称 M 为图 G(V,E) 的最大匹配。

当图 G(V,E) 是一个二分图时，由于其若含有环，则一定是偶环（一个点数为 2k 的环），其最大匹配可以使用匈牙利算法或网络流算法来求解。

当图 G(V,E) 是一个一般图时，由于一般图会含有奇环（一个点数为 2k+1 的环），而经过一个奇环会得到两条含有同一个点的匹配边，因此当图 G(V,E) 是一个一般图时，无法直接进行增广，需要用改进算法来求解最大匹配，即带花树算法。

【带花树算法】

带花树算法仍是分 n 个阶段寻找增广路，由于问题出在奇环上，那么首先分析一下奇环的性质。

奇环中有 2k+1 个点，所以最多有 k 组匹配，也就是说有一个点没有匹配，即这个点在环内两边的连边都不是匹配边，也只有这个点可以向环外连边。

根据这个性质，可以将奇环缩成一个点（这个点称为花），由于增广路经过奇环，那么奇环内的增广路可以还原出来，因此缩完点后的图如果可以找到一条增广路，那么原图中也可以找到一条增广路。

根据上述思想，整个求解过程可以分成 n 个阶段，每个阶段从没有匹配的 S 点开始 BFS 寻找增广路。

搜索的开始，将 S 点加入队列中，标记为 A 类点，如果从 x 点出发，搜索到一个未标记点，那么有两种情况：

1）如果这个未标记点 x 有匹配：将这个点设为 B 类点，它的匹配点设为 A 类点，加入队列继续增广。

2）如果这个未标记点 x 没有匹配：由于是从一个未匹配点开始进行搜索的，所以这说明找到了一条增广路，沿着过来的边找回去，展开带花树，在搜索的过程中，如果遇到了环，又有两种情况：

    ①修改搜索的过程中，如果遇到偶环：那么由于其不影响求解，因此不用管它
    ②修改搜索的过程中，如果遇到奇环：那么找到当前点 x 和找到的点 y，求出他们最近公共花祖先，然后用并查集缩掉环。

在缩环的时候，维护一个 pre 数组，表示回跳的时走到这里该往哪一个方向走回去。回跳的时候，每次找到 pre，然后修改这条边，接着跳到 pre 原来的 match 处。

如果倒着进入一个花的时候，上方的边为非匹配边，那么我们会往下走，这个时候 pre 就应该往下设，中间相遇的位置 pre 互相连接，即：pre[x]=y,pre[y]=x

时间复杂度：由于算法分为 n 个阶段，每个阶段最多把整个图遍历一次，每个点会最多被缩 n 次花，所以总复杂度为 O(n3)

【模版】

struct Edge {int to,next; } edge[N*N*2]; int head[N],tot; int n;//n个点 int father[N],pre[N];//father记录一个点属于哪个一个点为根的花 int Q[N*N*2],first,tail;//bfs队列 int match[N];//匹配 bool odd[N],vis[N];//odd记录一个点为奇点/偶点，1为奇，0为偶 int timeBlock;//LCA时间戳 int top[N],rinedge[N];void addEdge(int x,int y) {//添边edge[tot].to=y;edge[tot].next=head[x];head[x]=tot++; } int Find(int x){//并查集寻找根节点if(father[x]!=x)return father[x]=Find(father[x]);return x; } int lca(int x, int y){//求解最近公共祖先timeBlock++;while(x){rinedge[x]=timeBlock;x=Find(top[x]);}x=y;while(rinedge[x]!=timeBlock)x=Find(top[x]);return x; } void blossom(int x, int y, int k) {//将奇环缩成一个点并将原来是奇点的点变为偶点并加入队列while(Find(x)!=Find(k)){pre[x]=y;y=match[x];odd[y]=false;Q[tail++]=y;father[Find(x)]=k;father[Find(y)]=k;x=pre[y];} } bool bfs(int s) {memset(top,0,sizeof(top));memset(pre,0,sizeof(pre));memset(odd,false,sizeof(odd));memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)father[i]=i;vis[s]=true;first=tail=0;Q[tail++]=s;while(first!=tail){int now=Q[first++];for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(!vis[to]){top[to]=now;pre[to]=now;odd[to]=true;vis[to]=true;if(!match[to]){int j=to;while(j){int x=pre[j];int y=match[x];match[j]=x;match[x]=j;j=y;}return true;}vis[match[to]]=true;top[match[to]]=to;Q[tail++]=match[to];}else if(Find(now)!=Find(to) && odd[to]==false) {int k=lca(now,to);blossom(now,to,k);blossom(to,now,k);}}}return false; }int main() {memset(head,-1,sizeof(head));memset(match,0,sizeof(match));tot=0;int m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addEdge(x,y);addEdge(y,x);}int res=0;for(int i=1;i<=n;i++)if(!match[i])res+=bfs(i);printf("%d\n",res);for(int i=1;i<=n;i++)printf("%d ",match[i]);printf("\n");return 0; }

【例题】

• 一般图最大匹配（UOJ-79）：点击这里
• 挑战NPC（洛谷-P4258）：点击这里

总结

以上是生活随笔为你收集整理的图论 —— 带花树算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。