所以這裡直接提供模板:
注意這裡必須要是無向圖
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
日月卦長您好,我想請問為什麼這份程式碼的複雜度是 O(V(E + V)) 的?第 18 行的 u = pa[v]; 看起來會爬過半個 blossom,在層層堆疊的 blossom 中可能會有邊被爬過 O(V) 次,這樣有可能會退化至 O(V^2(E + V)),但我構造不出反例 ><
回覆刪除