[uoj79][带花树]一般图最大匹配

传送门：

http://uoj.ac/problem/79

一般图最大匹配不会做怎么办。看了一晚上的带花树没看明白。

思考一下带花树的核心是bfs()+缩花+增广

bfs大家都会，缩花是整个算法的难点。

玄学乱搞

假设我们不想写带花树并需求一个通常情况下可以解决一般图最大匹配问题的做法时，我们可以忽略掉缩花的过程然后随机增广，将未匹配点随机转移，通常可以在n^2时间内出正确解。

带花树

建议先看一下别人的讲义再看我这份，仅仅是部分补充。

https://www.cnblogs.com/owenyu/p/6858508.html

在二分图匹配中，我们通常使用匈牙利算法（fake）来解决最大匹配问题。考虑在一般图上使用匈牙利，我们发现有的点既成为了内点又成为了外点。思考在二分图上显然是不会出现这种情况的。容易发现这种情况下肯定是出现了一个奇环，而且这个环上如果有一个点出现了新的匹配，显然这个环上的所有点都得到了匹配，那么我们的匹配数+1（增广成功）。可以简单的推断出奇环上所有点的匹配情况是等价的，所以我们可以把它们缩起来。

那么我们要怎么实现这个做法呢？我一开始的想法是暴力的缩点，缩掉的点就直接不存在了。观察了一波网上大爷们的实现，我们并不需要显式的维护缩起来的点和重新建边，而是考虑使用一个并查集来简单的维护花根，用match数组表示一个点的配偶是谁，pre数组记录当一个点的配偶得到匹配时，这个点应该和谁匹配。考虑到一个花的形态就是从一个root走出2条未匹配边，然后这两条边走到了一起，那么缩点实际上非常简单了，我们一直走他的祖先，把一路上的点的花根全部指向root。理论上一个花中的节点已经全部指向花根了，并且在我的理解中这些点已经完全没有用了，因为这些结点的匹配状况相同，所以这些点的match等等我们也应该全部不关心，因为答案其实就是所有花根的图中的match数+花根size/2，但是因为我们是非显性维护的花，如果不把这些玩意的match维护出来的话，我们在缩点的时候就不好走他的祖先了，而且队列中的点如果仅仅是作为花根的一个延伸，那我们bfs的时候还得先把这个花根的儿子全部找出来，那我们还不如把它缩了。而且有的题要求输出match方案，所以还是用这种写法好点。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=;
const int M=;
int n,m;
namespace flowey
{
    int pre,tim,t,w,q[M],fa[N],last[N],match[N],col[N];
    int tot,nex[M],go[M],fir[N],vis[N];
    inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline void add(int x,int y) {nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;}
    inline int lca(int x,int y)
    {
        for(++tim,x=find(x),y=find(y);;swap(x,y))
        if(x)
        {
            if(vis[x]==tim) return x;
            vis[x]=tim;
            x=find(last[match[x]]);
        }
    }
    inline void link(int x,int y,int rt)
    {
        while(find(x)!=rt)
        {
            last[x]=y;
            if(fa[x]==x) fa[x]=rt;
            y=match[x];
            x=last[y];
            if(fa[y]==y) fa[y]=rt;
            if(col[y]==) col[q[++w]=y]=;
        }
    }
    inline int bfs(int X)
    {
        int u,e,v;
        for(int i=;i<=n;++i) fa[i]=i,col[i]=last[i]=;
        t=;col[q[w=1]=X]=;
        while(t<w)
        {
            u=q[++t];
            for(e=fir[u];v=go[e],e;e=nex[e])
            if(!col[v])
            {
                last[v]=u;
                if(!match[v])
                {
                    for(;u;v=pre,u=last[v])
                    //这个时候已经不需要像link一样修改last了，已经没有意义了 
                    {
                        pre=match[u];
                        match[u]=v;
                        match[v]=u;
                    }
                    return ;
                }
                col[v]=;
                col[q[++w]=match[v]]=;
            }
            else if(col[v]==&&find(u)!=find(v))
            {
                int k=lca(u,v);
                link(u,v,k);link(v,u,k);
            }
        }
        return ;
    }
}
int main()
{
//  freopen("79.in","r",stdin);
    using namespace flowey;
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    int ans=;
    for(int i=;i<=n;++i)
    if(!match[i]) ans+=bfs(i);
    cout<<ans<<endl;
    for(int i=;i<=n;++i) printf("%d ",match[i]);
}