一般图最大匹配学习笔记
Uoj #79
Luogu P6113
带花树算法（匈牙利算法 \(Pro~max\)）
我们考虑现在访问到 \(u\) 点（黑色），\(u\) 连向 \(v\) 点，分类讨论 \(v\) 点。
1、\(v\) 点没有被匹配过，直接令 \(u\) 点和 \(v\) 点匹配，然后更新答案
2、\(v\) 点匹配过，但之前还未被访问过，那么把 \(v\) 点染成白色，然后把 \(v\) 点的匹配点 \(x\) 加入队列，继续寻找增广路，并将 \(x\) 染成黑色。
3、\(v\) 点匹配过，且之前被访问过，是白色的，那么我们找到了一个偶环，那么我们无需任何操作，因为 \(v\) 点已经被找过一次了，无需再找一次
4、\(v\) 点匹配过，且之前被访问过，是黑色的，那么问题来了，我们找到了一个奇环，因为我们可以将那个黑点变成白点，然后继续循环下去，直到 \(TLE\)。
考虑怎么处理奇环呢？这就是带花树算法的精髓了。
我们发现，奇环的黑白点取决于奇环中的哪些点向奇环外的点匹配。那么我们考虑将环缩成点，这个过程就被成为“开花”。
不妨设 \(pre_i\) 表示白点 \(i\) 连向哪个黑点，\(match_i\) 表示 \(i\) 的匹配点。
考虑使用并查集记录每个奇环的顶点，缩环的时候将环上的点直接连向奇环的顶点即可，然后将环上的点变成黑色
但是因为我们可能经过多次缩环，所以有可能出现并查集使用路径压缩时已经不是该环的顶点了，所以我们考虑沿着 \(pre\) 和 \(match\) 往前一直走即可
讲了这么多，就是为了处理奇环，现在总结一下：如果这个奇环缩过，那么跳过，如果没有缩过，那么通过 \(pre\) 和 \(match\) 缩环并将环上的点染成黑色，然后继续循环
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1010;
ll n,m;
vector<ll> e[N];
ll match[N];
ll f[N],pre[N],bz[N],ti;
ll d[N],tot;
ll getf(ll x)
{
if(f[x]==x) return x;
return f[x]=getf(f[x]);
}
ll bp[N];
ll lca(ll x,ll y)
{
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(ll x,ll y,ll w)
{
while(getf(x)!=w)
{
pre[x]=y,y=match[x];
if(bz[y]==2) bz[y]=1,d[++tot]=y;
if(getf(x)==x) f[x]=w;
if(getf(y)==y) f[y]=w;
x=pre[y];
}
}
bool find(ll st)
{
for(ll i=1;i<=n;i++) f[i]=i,pre[i]=bz[i]=0;
d[tot=1]=st,bz[st]=1;
ll l=0;
while(l<tot)
{
ll now=d[++l];
for(ll i=0;i<e[now].size();i++)
{
ll to=e[now][i];
if(getf(to)==getf(now)||bz[to]==2) continue;
if(!bz[to])
{
bz[to]=2;
pre[to]=now;
if(!match[to])
{
for(ll x=to,y;x;x=y) y=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;
return 1;
}
bz[match[to]]=1,d[++tot]=match[to];
}
else
{
ll w=lca(now,to);
make(now,to,w);
make(to,now,w);
}
}
}
return 0;
}
int main()
{
scanf("%lld %lld",&n,&m);
ll x,y;
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
ll ans=0;
for(ll i=1;i<=n;i++)
if(!match[i]) ans+=find(i);
printf("%lld\n",ans);
for(ll i=1;i<=n;i++)
printf("%lld ",match[i]);
return 0;
}