Processing math: 0%
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}}

2016年7月15日 星期五

[ Edmonds's general graph matching algorithm ] 一般圖最大匹配

關於匹配的教學我全部寫在這份投影片裡了:https://jacky860226.github.io/general-graph-weighted-match-slides/#/
所以這裡直接提供模板:
注意這裡必須要是無向圖
#define MAXN 505
vector<int>g[MAXN];//用vector存圖
int pa[MAXN],match[MAXN],st[MAXN],S[MAXN],vis[MAXN];
int t,n;
inline int lca(int u,int v){//找花的花托
for(++t;;swap(u,v)){
if(u==0)continue;
if(vis[u]==t)return u;
vis[u]=t;//這種方法可以不用清空vis陣列
u=st[pa[match[u]]];
}
}
#define qpush(u) q.push(u),S[u]=0
inline void flower(int u,int v,int l,queue<int> &q){
while(st[u]!=l){
pa[u]=v;//所有未匹配邊的pa都是雙向的
if(S[v=match[u]]==1)qpush(v);//所有奇點變偶點
st[u]=st[v]=l,u=pa[v];
}
}
inline bool bfs(int u){
for(int i=1;i<=n;++i)st[i]=i;//st[i]表示第i個點的集合
memset(S+1,-1,sizeof(int)*n);//-1:沒走過 0:偶點 1:奇點
queue<int>q;qpush(u);
while(q.size()){
u=q.front(),q.pop();
for(size_t i=0;i<g[u].size();++i){
int v=g[u][i];
if(S[v]==-1){
pa[v]=u,S[v]=1;
if(!match[v]){//有增廣路直接擴充
for(int lst;u;v=lst,u=pa[v])
lst=match[u],match[u]=v,match[v]=u;
return 1;
}
qpush(match[v]);
}else if(!S[v]&&st[v]!=st[u]){
int l=lca(st[v],st[u]);//遇到花,做花的處理
flower(v,u,l,q),flower(u,v,l,q);
}
}
}
return 0;
}
inline int blossom(){
memset(pa+1,0,sizeof(int)*n);
memset(match+1,0,sizeof(int)*n);
int ans=0;
for(int i=1;i<=n;++i)
if(!match[i]&&bfs(i))++ans;
return ans;
}
view raw blossom.cpp hosted with ❤ by GitHub

1 則留言:

  1. 日月卦長您好,我想請問為什麼這份程式碼的複雜度是 O(V(E + V)) 的?第 18 行的 u = pa[v]; 看起來會爬過半個 blossom,在層層堆疊的 blossom 中可能會有邊被爬過 O(V) 次,這樣有可能會退化至 O(V^2(E + V)),但我構造不出反例 ><

    回覆刪除