引入

帶花樹解決的是一般圖的最大匹配問題。

學習此算法前你需要掌握二分圖匹配的匈牙利算法，至少需要知道它的思想。

理論

眾所周知，二分圖匹配的思想是不斷地找增廣路。

嚴謹?shù)刂v，是找到了一條簡單路徑，它的起點和終點都未匹配，并且路徑上的邊是 匹配邊-非匹配邊 相互交錯。

但是在一般圖中直接找增廣路會出鍋。

原因是二分圖中可以保證增廣的過程中匹配邊都是從左邊連到右邊，但一般圖中因為奇環(huán)的存在，使得這個方向是不定的。具體的原因不（lan）再（de）說明，自己畫個圖就可以看出。

我們注意到，二分圖和一般圖最本質，或者說唯一的區(qū)別就是是否存在奇環(huán)。

注：對于這個奇環(huán)雖然不一定簡單，但直接把它當成簡單環(huán)處理，后面會詳細說明。

我們發(fā)現(xiàn)對于一個大小為$2k+1$的奇環(huán)，從任意一個點都可以向外匹配，并且環(huán)內剩下的$2k$個點可以組成$k$對匹配。

這么說的話，環(huán)上的每個點都是等效的。

這么說我們可以直接把這$2k+1$個點縮成一個點處理，我們把縮成的點稱為"花"。

然后繼續(xù)增廣就可以了。

流程

前面說著簡單其實全在口胡……本算法的難點全在實現(xiàn)上。

記錄每個點的匹配點$m_i$,如果沒有匹配$m_i=0$,顯然初始時$m_i=0$

首先枚舉所有結點，當發(fā)現(xiàn)一個未匹配點(即$m_i=0$)時，嘗試從這個點為起點找一條增廣路。

設這個點為$s$,從$s$為根開始做 BFS 建出一棵帶花樹。注意帶花樹是對一個根單獨建的，也就是每次都要清空數(shù)據(jù)。

因為我們要找出增廣路翻轉，對每個結點$i$記錄一個前驅 $pr{e}_i$,表示如果以$s$為增廣路起點，$i$為終點，路徑上的倒數(shù)第二個點(也就是$i$往上跳一個點)是哪個。

值得注意的是，找增廣路的時候并不是一直跳$pr{e}_i$,因為增廣路是交替的，跳一步之后下一步一定是匹配邊。

所以跳一步$pre$后直接走到對應的匹配點,即不斷地$i\leftarrow m_{pr{e}_i}$，這在后面將很有用。

對點進行染色。一個點有三種狀態(tài)：黑色，白色，未染色。開始時所有點都未染色。然后起點$s$設為黑色。

每次從隊列中取出一個點$u$，從后面的流程可以知道它一定是黑點。

訪問所有與$u$相鄰的點$v$，然后大力分類討論。

$u$和$v$在一個花中（也就是被縮成了一個點）

不知道咋處理，但腦電波一下應該沒啥影響，所以跳過好了。

$v$是白色

似乎還是沒啥用，跳過好了。

$v$未染色

如果 $v$沒有被匹配，那么我們就找到了一條增廣路，跳$pre$翻轉所有邊的匹配狀態(tài)，答案$+1$,退出函數(shù)。

否則我們把$v$染成白色，并令$pr{e}_v=u$。因為$v$已經(jīng)有匹配了，我們把$m_v$染成黑色并壓進隊列，表示從可以這里開始增廣。

$v$是黑色

最復雜的情況。當找到一個黑色的時候說明出現(xiàn)了一個奇環(huán)。

因為是 bfs，我們可以暴力跳$pre$找到以$s$為根時$u$和$v$的 LCA ，記為$p$

我們需要把這條路徑上的點合并。

可以用并查集維護，把路徑上的點并查集的父親設為$p$就可以了。注意花里面可能套了花，所以只考慮并查集的根。

然而還沒完，因為你還要求出具體的匹配點，所以你需要維護環(huán)內的匹配情況。

圖例：粗邊為匹配邊，細邊為未匹配邊，箭頭為$pre$

為了貫徹落實“任何一個點都可以向外匹配”的性質，盯著這個圖，發(fā)現(xiàn)任何一個黑點（即所有匹配邊的下面那個）在外面有匹配邊的時候，都可以向上整一條增廣路出來。

以$v$為例：

我們想讓白點（匹配邊上面那個）也可以整一個出來，不難構造出

地 獄 繪 圖

這樣利用找增廣路是隔一次跳一步的性質，白點會從下面繞一圈上去，完美地解決了這個問題。具體實現(xiàn)見代碼。

然后在跳的過程中把白點染成黑點并入隊，表示歡迎外面的點進來找增廣路。

如果你不知道為什么原來就是黑色的點不入隊，想想你把它染成黑色的時候在干什么。

總復雜度是$O(n^3)$，實際上很松，可以當$O(n^2)$算

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <queue> #define MAXN 1005 #define MAXM 100005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } int mat[MAXN],pre[MAXN],col[MAXN],fa[MAXN],n,m; int idx[MAXN],tot; inline int find(const int& x){return x==fa[x]? x:fa[x]=find(fa[x]);} queue<int> q; inline int lca(int x,int y) {for (++tot;;swap(x,y))if (x){x=find(x);if (idx[x]==tot) return x;idx[x]=tot,x=pre[mat[x]]; } } inline void shrink(int x,int y,int l) {while (find(x)!=l){pre[x]=y,y=mat[x];if (col[y]==2) col[y]=1,q.push(y);if (x==find(x)) fa[x]=l;if (y==find(y)) fa[y]=l;x=pre[y];} } inline int bfs(int s) {while (!q.empty()) q.pop();q.push(s);col[s]=1;for (int i=1;i<=n;i++) pre[i]=col[i]=0,fa[i]=i;while (!q.empty()){int u=q.front();q.pop();for (int i=head[u];i;i=nxt[i]){int v=e[i].v;if (col[v]==2||find(u)==find(v)) continue;if (!col[v]){col[v]=2,pre[v]=u;if (!mat[v]){for (int last;v;v=last)last=mat[pre[v]],mat[v]=pre[v],mat[pre[v]]=v;return 1;}col[mat[v]]=1,q.push(mat[v]);}else{int l=lca(u,v);shrink(u,v,l),shrink(v,u,l);}}}return 0; } int main() {n=read(),m=read();for (int i=1;i<=m;i++){int u,v;u=read(),v=read();addnode(u,v),addnode(v,u);}for (int i=1;i<=n;i++) fa[i]=i;int ans=0;for (int i=1;i<=n;i++)if (!mat[i])ans+=bfs(i);printf("%d\n",ans);for (int i=1;i<=n;i++) printf("%d%c",mat[i]," \n"[i==n]);return 0; }

總結

以上是生活随笔為你收集整理的带花树学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

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