首页 > 分享 > 带花树算法解析

带花树算法解析

花匠小妙招
2025-07-27 16:06

参考 b l o g blog blog:
r q y rqy rqy , 租酥雨 , F u y u k i Fuyuki Fuyuki

前置知识

匈牙利算法求解二分图最大匹配

正题

众所周知,带花树是用来求解一般图最大匹配的算法.

那么为啥匈牙利算法不行呢?(废话,不然为啥要有这个算法?)

(转自 r q y rqy rqy)
原因是：我们在二分图中，如果 d f s dfs dfs找增广路时经过某个点找不到，那么我们可以证明这一轮中这个点的确是无用的（也即，这一轮里所有的增广路都不经过这个点），于是我们就能保证每个点至多走一遍，时间复杂度 O ( n m ) O(nm) O(nm).但是如果是一般图，这个性质不一般成立。比如下图：

图中红线是已匹配的边。那么，如果我从 1 1 1开始dfs时先经过 2 2 2，那么接下来就只能到 4 4 4（因为只能走匹配边），然后是 5 , 3 5,3 5,3，同时我们会给这四个节点都打一个“找不到增广路”的标记。
但是实际上存在 1 → 3 → 5 → 4 → 2 → 6 1→3→5→4→2→6 1→3→5→4→2→6这条增广路。仔细观察我们就能发现：这种现象之所以存在，是由于奇环 1 − 3 − 5 − 4 − 2 − 1 1-3-5-4-2-1 1−3−5−4−2−1的存在（如果没有奇环，就变成了二分图匹配，这时候匈牙利算法就是对的）。

可以发现奇环内只能有一个点连向外部,就等价于我们对这个奇环缩点,在新图的基础上跑一般图最大匹配.

算法流程:

我们对这张图进行黑白染色,以确定奇环/偶环.
每次把一个未匹配点加入,尝试 b f s bfs bfs增广.
我们把这个点记为黑点,并加入队列.取出队头 x x x,取出邻接点 y y y.有以下情况 y y y为白,那么这是一个偶环,没有增广的价值,跳过 y y y为黑,那么这是一个奇环,进行缩点处理. y y y无色,此时标记为白色.
如果 y y y无 m a t c h match match,那么增广完成,对前面的 m a t c h match match进行修改.
否则,把 y 的 m a t c h y的match y的match加入队列.

模板

#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=1e5+10; void qr(int &x) {scanf("%d",&x); } int n,m,fa[N],col[N],mat[N],pre[N],ans,q[N],l,r; struct edge{int y,next;} a[M]; int len,last[N]; void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;} int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);} int dfn[N],id; int lca(int x,int y) { for(id++; ;swap(x,y)) if(x) { if(dfn[x=get(x)]==id) return x; dfn[x]=id; x=pre[mat[x]]; } } void blossom(int x,int y,int z) { while(get(x)^z) { pre[x]=y; y=mat[x]; if(col[y]==2) col[y]=1,q[++r]=y; fa[x]=fa[y]=z; x=pre[y]; } } bool bfs(int x ){ for(int i=1;i<=n;i++) fa[i]=i,col[i]=pre[i]=0; q[l=r=1]=x; col[x]=1; for( ;l<=r;x=q[++l]) { for(int k=last[x],y,z;k;k=a[k].next) { y=a[k].y; if(col[y]==2||get(x)==get(y)) continue; if(col[y]) {z=lca(x,y); blossom(x,y,z); blossom(y,x,z); } else { col[y]=2; pre[y]=x; if(!mat[y]) { while(y) x=pre[y],z=mat[x],mat[x]=y,mat[y]=x,y=z; return 1; } if(!col[mat[y]]) {col[mat[y]]=1; q[++r]=mat[y];} } } } return 0; } int main() { qr(n); qr(m); for(int i=1,x,y;i<=m;i++) qr(x),qr(y),ins(x,y),ins(y,x); for(int i=1;i<=n;i++) ans += !mat[i]&&bfs(i); printf("%dn",ans); for(int i=1;i<=n;i++) printf("%d ",mat[i]); return 0; }

cpp

运行

复杂度证明

每次 b f s bfs bfs对 n n n点 m m m边都扫描一遍,每次就是 O ( n + m ) O(n+m) O(n+m).
b l o s s o m blossom blossom:暴力更新连通块, O ( n 2 ) O(n^2) O(n2)

至多进行 O ( n ) O(n) O(n)次 b f s bfs bfs,所以复杂度为 O ( n ( n 2 + m ) ) O(n(n^2+m)) O(n(n2+m)).

例题

1 or 2

有 n n n个点 m m m条边,你需要删掉一些边使得每个点 i i i的度数为 D [ i ] ( D [ i ] = 1 o r 2 ) D[i](D[i]=1 ~or~ 2) D[i](D[i]=1 or 2).
判断是否有合法方案.(其实把删的边输出也不难)
( n ≤ 50 , m ≤ 100 ) (nle 50,mle 100) (n≤50,m≤100).

为了防止每条边被删除2次,我们把边拆为两个点(入点,出点).
对于 D [ i ] = 2 D[i]=2 D[i]=2的点,我们也拆点.

入点和 x x x的集合连边,出点和 y y y集合连边,最后入点出点连边.

此时如果出现完美匹配,则有合法解.

如果入点不被出点选择,那么出点一定会选择一个点,其实这样对应着原图的一条边.
否则,入点选择出点代表这条边被删除,并没有对度数造成影响.

#include<bits/stdc++.h> #define fi first #define se second #define lc (x<<1) #define rc (x<<1|1) #define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++) #define mk make_pair #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define IT iterator #define vi vector<int> #define TP template<class o> #define SZ(a) ((int)a.size()) #define all(a) a.begin(),a.end() using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N=310,M=1010,size=1<<20,mod=998244353,inf=2e9; //char buf[size],*p1=buf,*p2=buf; template<class o> void qr(o &x) { char c=gc; x=0; int f=1; while(!isdigit(c)){if(c=='-')f=-1; c=gc;} while(isdigit(c)) x=x*10+c-'0',c=gc; x*=f; } template<class o> void qw(o x) { if(x/10) qw(x/10); putchar(x%10+'0'); } template<class o> void pr1(o x) { if(x<0)x=-x,putchar('-'); qw(x); putchar(' '); } template<class o> void pr2(o x) { if(x<0)x=-x,putchar('-'); qw(x); puts(""); } int n,m,D[N],ID[N],fa[N],mat[N],col[N],pre[N],q[N],l,r,ans,tot; struct edge{int y,next; } a[M]; int len,last[N]; void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;} void add(int x,int y) {ins(x,y); ins(y,x);} int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);} int dfn[N],id; int lca(int x,int y){ for(++id; dfn[x=get(x)]!= id; swap(x,y)) dfn[x]=id,x=pre[mat[x]]; return x; } void blossom(int x,int y,int z) { while(get(x)^z) { pre[x]=y; y=mat[x]; if(col[y]==2) q[++r]=y,col[y]=1; fa[x]=fa[y]=z; x=pre[y]; } } bool bfs(int x) { for(int i=1;i<=tot;i++) fa[i]=i,col[i]=pre[i]=0; col[x]=1; q[l=r=1]=x; for( ;l<=r;x=q[++l]) { for(int k=last[x],y,z;k;k=a[k].next) { y=a[k].y; if(col[y]==2||get(x)==get(y)||y==mat[x]) continue; if(col[y]) {z=lca(x,y); blossom(x,y,z); blossom(y,x,z); } else { col[y]=2; pre[y]=x; if(!mat[y]) { while(y) x=pre[y],z=mat[x],mat[x]=y,mat[y]=x,y=z; return 1; } if(!col[mat[y]]) {col[mat[y]]=1; q[++r]=mat[y];} } } } return 0; } int solve() { ans=0; for(int i=1;i<=tot;i++) mat[i]=0; for(int i=1;i<=tot;i++) ans += !mat[i]&&bfs(i); return ans*2==tot; } int main() { while(~scanf("%d%d",&n,&m)) { len=0; memset(last,0,sizeof last); tot=0; for(int i=1;i<=n;i++) ID[i]=++tot,qr(D[i]),tot+=D[i]-1; for(int i=1,x,y,z;i<=m;i++) { qr(x); qr(y); z=++tot; add(ID[x],z); if(D[x]>1) add(ID[x]+1,z); add(tot,tot+1); z=++tot; add(ID[y],z); if(D[y]>1) add(ID[y]+1,z); } if(tot&1) puts("No"); else if(solve()) puts("Yes"); else puts("No"); } return 0; }

cpp

运行

daizhenyang’s chess

有 n ∗ m n*m n∗m的网格,有一些幸运点和不幸点.每个格子的移动范围为20个格子.
有一个国王棋子. 两个绝顶聪明的人玩游戏,每次移动国王棋子到未到达过的幸运点,最后不能移动者输.
问先手是否必胜.

如果国王一定在最大匹配内,那么先手走匹配边,后手走非匹配边,最后先手必胜.
否则,国王的后继都一定在最大匹配内(反证法可证:如有一个不符合就有一个更大的匹配),所以后手必胜.

#include<bits/stdc++.h> using namespace std; const int N=255; int T,n,m,id[17][17],tot,fa[N],pre[N],col[N],mat[N],q[N*2],l,r,king; struct edge{int y,next; } a[N*22]; int len,last[N]; void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;} int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} int dfn[N],num; int lca(int x,int y) { for(++num; ;swap(x,y)) if(x) { if(dfn[x=get(x)]==num) return x; dfn[x]=num; x=pre[mat[x]]; } for(++num; dfn[x=get(x)]!=num; swap(x,y)) ... } void blossom(int x,int y,int z) { while(get(x)!=z){ pre[x]=y; y=mat[x]; if(col[y]==2) q[++r]=y,col[y]=1; fa[x]=fa[y]=z; x=pre[y]; } } bool bfs(int x) { for(int i=1;i<=tot;i++) fa[i]=i,col[i]=pre[i]=0; q[l=r=1]=x; col[x]=1; for( ;l<=r;x=q[++l]) { for(int k=last[x],y,z; k;k=a[k].next) { y=a[k].y; if(col[y]==2 || get(x)==get(y)) continue; if(col[y]) {z=lca(x,y); blossom(x,y,z); blossom(y,x,z); } else { col[y]=2; pre[y]=x; if(!mat[y]) { while(y) {x=pre[y]; z=mat[x]; mat[x]=y,mat[y]=x; y=z;} return 1; } q[++r]=mat[y]; col[mat[y]]=1; } } } return 0; } bool check() { for(int i=1;i<=tot;i++) mat[i]=0; for(int i=1;i<=tot;i++) if(!mat[i]&&i!=king) bfs(i); return bfs(king); } void qr(int &x) {scanf("%d",&x); } char s[17][17]; bool pd(int x,int y) {return 0<x&&x<=n&&0<y&&y<=m&&s[x][y]=='.';} int main() { qr(T); for(int t=1;t<=T;t++) { tot=0; len=0; memset(last,0,sizeof last); qr(n); qr(m); for(int i=1;i<=n;i++) { scanf("%s",s[i]+1); for(int j=1;j<=m;j++) { if(s[i][j]!='#') id[i][j]=++tot; if(s[i][j]=='K') king=tot; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]!='#') for(int dx=-2;dx<=2;dx++) for(int dy=-2;dy<=2;dy++) if( (!dx&&dy%2==0) || (!dy&&dx%2==0) || !pd(i+dx,j+dy)) continue; else ins(id[i][j],id[i+dx][j+dy]); printf("Case #%d: daizhenyang %sn",t,check()?"win":"lose"); } return 0; }

cpp

运行

luogu P4258 [WC2016]挑战NPC

n n n个球, m m m个筐,每筐至多放三个球.
给定一些球筐的合法放置选择.
求最大半空球筐数(半空为至多放一个球).

2 , 3 → 1 2,3rightarrow 1 2,3→1(球筐剩余 x x x为2,3 的贡献 y y y均为1),可以发现 y = ⌊ x 2 ⌋ y=lfloor dfrac x 2rfloor y=⌊2x⌋,这就是一个最大匹配数啊.

所以我们把一个筐拆成一个三角形,连边也拆成三条.
为了先保证每个球都能放入,所以先让球增广,带花树有个特点就是不会改变匹配点为未匹配点,所以就能保证正确啦~~~

#include<bits/stdc++.h> using namespace std; const int N=610,M=N*N; void qr(int &x) {scanf("%d",&x);} int T,n,m,e,fa[N],pre[N],mat[N],q[N],l,r,col[N],ans,tot,ID[N]; struct edge{int y,next; } a[M]; int len,last[N]; void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;} void add(int x,int y) {ins(x,y); ins(y,x); } int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);} int dfn[N],id; int lca(int x,int y) { for(id++; ;swap(x,y)) if(x) { if(dfn[x=get(x)]==id) return x; dfn[x]=id; x=pre[mat[x]]; } } void blossom(int x,int y,int z) { while(get(x)^z) { pre[x]=y; y=mat[x]; if(col[y]==2) q[++r]=y,col[y]=1; fa[x]=fa[y]=z; x=pre[y]; } } bool bfs(int x) { for(int i=1;i<=tot;i++) fa[i]=i,col[i]=pre[i]=0; q[l=r=1]=x; col[x]=1; while(l<=r) { x=q[l++]; for(int k=last[x],y,z; k;k=a[k].next) { y=a[k].y; if(col[y]==2 || get(x)==get(y)) continue; if(col[y]) {z=lca(x,y); blossom(x,y,z); blossom(y,x,z); } else { col[y]=2; pre[y]=x; if(!mat[y]) { while(y) x=pre[y],z=mat[x],mat[x]=y,mat[y]=x,y=z; return 1; } y=mat[y]; q[++r]=y; col[y]=1; } } } return 0; } int main() { qr(T); while(T--) { qr(n); qr(m); qr(e); len=0; memset(last+1,0,sizeof(int[tot])); tot=3*m; for(int i=1;i<=m;i++) { int x=3*i; add(x,x-1); add(x,x-2); add(x-1,x-2); } for(int i=1;i<=n;i++) ID[i]=++tot; while(e--) { int x,y; qr(x); qr(y); x=ID[x]; y=3*y; for(int i=0;i<3;i++) add(x,y--); } ans=0; for(int i=1;i<=tot;i++) mat[i]=0; for(int i=3*m+1;i<=tot;i++) bfs(i); for(int i=3*m; i;i--) ans+=!mat[i]&&bfs(i); printf("%dn",ans); for(int i=3*m+1;i<tot;i++) printf("%d ",(mat[i]+2)/3); printf("%dn",(mat[tot]+2)/3); } return 0; }

cpp

运行