Text

一般圖的最大匹配仍然是基于尋找增廣路的

增廣路的定義是這樣的一條路徑，它不經過重復的點，并且路徑兩端均沒有匹配，且整條路徑是非匹配邊-匹配邊-非匹配邊這樣交錯的。

類比二分圖最大匹配的增廣路算法，如果我們找到了一條增廣路，那么將這條增廣路的邊取反（匹配的變成非匹配，非匹配的變成匹配），那么匹配數會恰好+1，如果全圖不存在增廣路，也就說明當前已經是一個最大匹配了。（證明略）

一般圖和二分圖的區別就在于有沒有邊數為奇數的環
那為什么一般圖最大匹配不能直接像二分圖那樣做呢？

考慮我們尋找增廣路的過程
（圖片引自 陳胤伯《淺談圖的匹配算法及其應用》，2015年國家集訓隊論文集）

我們在尋找增廣路的時候，會將路徑上的點黑白染色，匹配只存在黑點與白點之間。

如果沒有環或者只有偶環，那么每個點的顏色（或者說奇偶性）是確定的
但如果出現了奇環，那么點的顏色就不再確定，因為奇環順時針走一圈和逆時針走一圈的結果是不同的。

怎么辦呢？

這就有了我們的帶花樹算法（名字我覺得很迷）

我們按照算法流程來一步步說明

仍然是從每個未匹配的點開始尋找增廣路，不過我們采用BFS的方式，每個點均設為無色，端點染成黑色
設當前點為u（黑色）,枚舉與它相鄰的點v

考慮v是否已經被訪問過

若v尚未訪問過（v為無色）
如果v尚未匹配，說明我們找到了一條增廣路，直接返回修改。
如果v已經匹配，那么將v染成白色，v的匹配點x加入隊列，繼續尋找增廣路，x染成黑色。

容易看出，根據上面的過程，我們只會對于黑點枚舉出邊，正確性是顯然的，并且我們訪問的路徑形成了一棵黑白點交錯的樹。

若v已經訪問過（有顏色），說明我們找到了一個環。
如果它是一個偶環（v為白色），那么v顯然已經被找過了，無需再找一次。

如果它是一個奇環（v為黑色），這就出鍋了
怎么辦呢？

如上圖，粗邊為匹配邊。
對于一個奇環，我們一定是從一個黑點進入，然后也在黑點碰頭(u,v)，（這個可以畫圖理解一下，如果不是從黑點進入，我們在之前訪問這個奇環時一定還沒有繞一圈就找到增廣路增廣了）

問題在于，此時對于整個奇環的顏色都不確定了，我們令這個奇環的頂點為最頂上的那一個黑點，那么考慮u上方的這一個白點，我們既可以走從頂點走一條非匹配邊到它，它作為一個黑點，也可以從另一邊轉一圈到它，此時這個它變成了黑點，它是需要加入隊列繼續走的

也就是說，對于一個奇環，它上面的點都可以成為黑點。
繼續觀察可以發現，整個奇環的匹配狀態只與頂點的匹配狀態有關，如果在后來的某一次尋找時奇環上的匹配被改變了，那么頂點的顏色唯一決定了整個環的匹配邊是如何走的。

也就是說，整個環就可以用一個頂點表示了，也就意味著我們可以將這個環縮掉，縮掉的環就稱為“花”，縮環就是開花

我們不妨對于每一個白點x，記pre[x]表示x是由哪一個黑點走過來的，也就是記錄了增廣路上的非匹配邊。
對于每一個點，記match[x]表示x的匹配點是誰。

縮環具體怎么縮呢？

如果直接修改原本的連邊比較麻煩，我們考慮采用并查集，記錄每個點所在的奇環的頂點，初始時就是它自己。縮環的時候，我們直接將環上的所有點并查集父親連向奇環的頂點，并將環上的白點都變成黑點，并且加入隊列。

此外，由于奇環可以雙向走，因此我們的pre邊也要變成雙向的。

容易發現，我們有可能經過了多次縮環，也就是說某一次縮環的一個點很有可能是縮過的一個環頂，我們在縮環以及找到增廣路返回修改的時候是需要走原來縮之前的環的，這個只需要沿著pre和match一直走即可，pre在這里相當于記錄了縮掉的環內部的走法。

現在我們來理一理思路

從每個未匹配的點BFS尋找增廣路，每個點均設為無色，端點染成黑色
枚舉與當前點u（黑色）相鄰的點v

考慮v是否已經被訪問過

若v尚未訪問過（v為無色）
如果v尚未匹配，找到了一條增廣路，直接返回修改。
如果v已經匹配，將v染成白色，將v的匹配點x加入隊列，繼續尋找增廣路，x染成黑色。

若v在當次增廣已經訪問過，找到環
v為白色，是一個偶環，跳過。
v為黑色且u,v所在的奇環已經縮過了，那么也跳過。

否則，v為黑色，找到一個新的奇環，那么找到u,v所在奇環的環頂（即它們在BFS上跑出來的交錯樹的lca，稱之為最近公共花祖先），將u到環頂的路徑以及v到環頂的路徑修改掉，白點染成黑點，加入隊列，并將環上的點（或者是某個已經縮了的環頂）并查集父親指向lca。

接下來就是代碼部分，我們可以結合代碼來理解上面的過程。

Code (UOJ #079)

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 505 #define M 130005 using namespace std; int n,m,m1,fs[N],nt[2*M],dt[2*M],pre[N],match[N],f[N],bz[N],bp[N],ti,d[N*N]; void link(int x,int y) {nt[++m1]=fs[x];dt[fs[x]=m1]=y; } int getf(int k) {return (f[k]==k)?k:f[k]=getf(f[k]); } int lca(int x,int y)//整個lca實現比較巧妙，由于是BFS，那么這兩個點在當前奇環上的深度一定相等，交替暴力尋找lca即可。 {ti++;x=getf(x),y=getf(y);while(bp[x]!=ti){bp[x]=ti;//此處僅僅是一個標記，無其他作用x=getf(pre[match[x]]);if(y) swap(x,y);}return x; } void make(int x,int y,int w)//縮環（開花）過程 {while(getf(x)!=w){pre[x]=y,y=match[x];//x是原本的黑點，y是原本的白點，將原本的pre邊變成雙向。if(bz[y]==2) bz[y]=1,d[++d[0]]=y;//若y還是白點則染黑if(getf(x)==x) f[x]=w;if(getf(y)==y) f[y]=w;x=pre[y];} } bool find(int st)//主過程 {fo(i,1,n) f[i]=i,pre[i]=bz[i]=0;d[d[0]=1]=st,bz[st]=1;int l=0;while(l<d[0]){int k=d[++l];for(int i=fs[k];i;i=nt[i]){int p=dt[i];if(getf(p)==getf(k)||bz[p]==2) continue;//如果找到一個已經縮過的奇環或者偶環則跳過if(!bz[p]){bz[p]=2,pre[p]=k;if(!match[p])//找到增廣路{for(int x=p,y;x;x=y) y=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;//返回修改匹配return 1;}bz[match[p]]=1,d[++d[0]]=match[p];//否則將其匹配點加入隊列}else {int w=lca(k,p);make(k,p,w);make(p,k,w);//以上分別修改k到lca的路徑以及p到lca的路徑（環的兩半）}}}return 0; } int main() {cin>>n>>m;fo(i,1,m){int x,y;scanf("%d%d",&x,&y);link(x,y),link(y,x);}int ans=0;fo(i,1,n) if(!match[i]) ans+=find(i);printf("%d\n",ans);fo(i,1,n) printf("%d ",match[i]); }

轉載于:https://www.cnblogs.com/BAJimH/p/10569418.html

總結

以上是生活随笔為你收集整理的【学习小记】一般图最大匹配——带花树算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。