带花树是一种用于解决一般图最大匹配的算法(不是数据结构)
一般图与二分图最大的不同是一般图中存在奇环，所以不能和二分图一样的随便找到一条交错路就增广。
带花树的做法是把奇环缩起来(开花)，让环上的点找到一个增广路之后能沿着正确的方向往回退，除此之外在思路上与匈牙利差不多。
具体看代码的注释
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
namespace Patchouli{
const int N=514,M=310000;
int n,m;
int head[N],ver[M],next[M],tot,num;
int match[N],pre[N],vis[N],f[N],time[N];
queue<int>q;
inline void add(int x,int y){
next[++tot]=head[x],head[x]=tot,ver[tot]=y;
next[++tot]=head[y],head[y]=tot,ver[tot]=x;
}
//并查集
int get(int x){
return x==f[x]?x:f[x]=get(f[x]);
}
inline int read(){
int a=1,b=0;char t;
do{t=getchar();if(t=='-')a=-1;}while(t>'9'||t<'0');
do{b=b*10-'0'+t;t=getchar();}while(t>='0'&&t<='9');
return a*b;
}
//在BFS树上找LCA,这个是最暴力的方法,可以记录一下depth让跳的合理一点(不过不影响最后的复杂度)
//这个time只是一个不用清空的vis数组
inline int LCA(int x,int y){
++num;
//轮流随便跳
//这里的x和y一定是黑点,模拟BFS的过程往回跳
//因为BFS是一次走两步的,所以lca也一定是一个黑点
while(true){
if(x){
x=get(x);
if(time[x]==num)return x;
else time[x]=num,x=pre[match[x]];
}
swap(x,y);
}
}
//开花
//奥妙重重的变换
//因为BFS是两步两步进行处理的,所以两个点同时跳
//x一直是原来的黑点,y除了第一个都是原来的白点
//原来只有白点会记录pre,现在黑点也可以记录pre,只是记录的pre是方向的(BFS树环上的儿子)
//原来的白点被标记为黑点,也和黑点一样进行扩展
//如果是被原来的白点扩展出来的增广路,会通过另一个方向进行取反
inline void blossom(int x,int y,int z){
while(get(x)^z){
pre[x]=y;y=match[x];
if(vis[y]==2)vis[y]=1,q.push(y);
f[x]=z,f[y]=z;
x=pre[y];
}
}
//pre表示在BFS树上的祖先
//match表示匹配的点
//vis是染色的状态,约定0为无色,1为黑色,2为白色,最开始增广的点是黑点
//只有黑点会进入队列,枚举出边
inline int BFS(int s){
//清空数组
while(q.size())
q.pop();
for(int i=1;i<=n;++i)
vis[i]=pre[i]=0,f[i]=i;
//初始点为黑点,加入队列
q.push(s);vis[s]=1;
//BFS
while(q.size()){
int x=q.front();
q.pop();
//枚举x的出边
for(int i=head[x];i;i=next[i]){
int y=ver[i];
//像匈牙利一样,走一条非匹配边走一条匹配边,所以如果这条已经是匹配边就不用走了(不加也不会出问题,因为就算把已经匹配的点加入队列,下一步就走不了了)
if(match[y]==x)continue;
//如果两个点被缩在一起了,或是另外一个点已经被标记为白点了(这表示它增广过了),continue
if(get(x)==get(y)||vis[y]==2)continue;
//如果这个点没有被染色,那么将它染为白色
if(!vis[y]){
vis[y]=2;
//记录父亲
pre[y]=x;
//如果y没有匹配,那么就已经可以增广了
if(!match[y]){
//沿途取反,同匈牙利
for(int o=y,last;o;o=last)
last=match[pre[o]],match[o]=pre[o],match[pre[o]]=o;
return 1;
}
vis[match[y]]=1,q.push(match[y]);
}
else {
//否则一定是一个黑点,因为当前点就是一个黑点,所以出现了奇环,进行开花
int z=LCA(x,y);
blossom(x,y,z);
blossom(y,x,z);
}
}
}
return 0;
}
int QAQ(){
//读入
n=read(),m=read();
int ans=0;
for(int i=1;i<=m;++i)
add(read(),read());
//和匈牙利差不多,如果一个点没有匹配就试图给它增广
for(int i=1;i<=n;++i)
if(!match[i])
ans+=BFS(i);
//输出答案
printf("%d
",ans);
for(int i=1;i<=n;++i)
printf("%d ",match[i]);
putchar('
');
return false;
}
}
int main(){
return Patchouli::QAQ();
}