【分析】
推荐博客：http://blog.csdn.net/yihuikang/article/details/10460997
http://blog.csdn.net/jackyguo1992/article/details/11271497
上模板：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 510
#define Maxm 1247501+100 int n; struct node
{
int x,y,next;
}t[Maxm*2];
int first[Maxn],len; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} int fa[Maxn],nt[Maxn],mark[Maxn],match[Maxn];
int vis[Maxn],nw;
int ffa(int x)
{
if(fa[x]!=x) fa[x]=ffa(fa[x]);
return fa[x];
} int merge(int x,int y)
{
fa[ffa(x)]=ffa(y);
} queue<int > q; //找环
int LCA(int x,int y)
{
nw++;
while(1)
{
if(x)
{
x=ffa(x);
if(vis[x]==nw) return x;
vis[x]=nw;
if(match[x]) x=nt[match[x]];
else x=0;
}
int tt=x;x=y;y=tt;
}
} //奇环缩点
void shrink(int x,int rt)
{
while(x!=rt)
{
int y=match[x],z=nt[y];
if(ffa(z)!=rt) nt[z]=y;
if(mark[y]==2) {q.push(y);mark[y]=1;}
if(mark[z]==2) {q.push(z);mark[z]=1;}
merge(x,y);merge(y,z);
x=z;
}
} void augment(int now)
{
nw=0;
for(int i=1;i<=n;i++)
nt[i]=0,vis[i]=0,mark[i]=0,fa[i]=i;
while(!q.empty()) q.pop();
q.push(now);mark[now]=1;
while(!q.empty())
{
int x=q.front();q.pop();
if(match[now]) return;//当前搜索节点找到增广路
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(match[x]==y||ffa(x)==ffa(y)) continue;
if(mark[y]==2) continue;
//奇环缩点
if(mark[y]==1)
{
int rt=LCA(x,y);
if(ffa(x)!=rt) nt[x]=y;
if(ffa(y)!=rt) nt[y]=x; shrink(x,rt);shrink(y,rt);
}
//增广
else if(!match[y])
{
nt[y]=x;
for(int j=y;j;)
{
int k=nt[j],z=match[k];
match[j]=k;match[k]=j;
j=z;
}
break;
}
//之前匹配过
else
{
nt[y]=x;
q.push(match[y]);
mark[match[y]]=1;
mark[y]=2;
}
}
}
} int main()
{
int m;
scanf("%d%d",&n,&m);
len=0;
memset(first,0,sizeof(first));
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
int ans=0;
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++) if(!match[i]) augment(i);
for(int i=1;i<=n;i++) if(match[i]) ans++;
ans/=2;
printf("%d\n",ans);
for(int i=1;i<=n;i++) printf("%d ",match[i]);
printf("\n");
return 0;
}
✿我认为所谓带花树的树，指匈牙利树，奇环缩点构成花✿
2017-03-04 11:26:08