uoj#79. 一般图最大匹配（带花树）

约定不等于承诺〃 2022-01-12 09:29 83阅读 0赞

[传送门][Link 1]

带花树

不加证明的说一下过程好了：每次从一个未匹配点\\(S\\)出发bfs，设\\(S\\)为\\(1\\)类点，如果当前点\\(v\\)在本次bfs中未经过，分为以下两种情况

1.\\(v\\)是未匹配点，那么从\\(S\\)到\\(v\\)的路径就是一条增广路，把这条路径增广即可

2.\\(v\\)是匹配点，那么把\\(v\\)设为\\(2\\)类点，并把\\(v\\)的匹配点扔进bfs的队列里

如果\\(v\\)已经经过了，且是一个\\(1\\)类点的话无视，否则如果是一个\\(2\\)类点，说明找到了一个奇环，把这个奇环缩成一个点（一朵花），并把上面的所有的点都标记为\\(2\\)号点并扔进bfs队列里

然后剩下的看代码吧……细节不要问我啊我自己都还没搞清楚呢QAQ

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    char sr[1<<21],z[20];int C=-1,Z=0;
    inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
    void print(R int x){
        if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
        while(z[++Z]=x%10+48,x/=10);
        while(sr[++C]=z[Z],--Z);sr[++C]='\n';
    }
    const int N=505,M=N*N;
    struct eg{int v,nx;}e[M];int head[N],tot;
    inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
    int fa[N],vis[N],Pre[N],match[N],ty[N],q[M];
    int h,t,tim,n,m,u,v,res;
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    int LCA(int x,int y){
        for(++tim;;swap(x,y))if(x){
            x=find(x);
            if(vis[x]==tim)return x;
            vis[x]=tim,x=Pre[match[x]];
        }
    }
    void shrink(int x,int y,int k){
        while(find(x)!=k){
            Pre[x]=y,y=match[x];
            if(ty[y]==2)ty[y]=1,q[++t]=y;
            if(find(x)==x)fa[x]=k;
            if(find(y)==y)fa[y]=k;
            x=Pre[y];
        }
    }
    bool path(int S){
        q[h=t=1]=S;
        fp(i,1,n)ty[i]=Pre[i]=0,fa[i]=i;
        while(h<=t){
            int u=q[h++];
            go(u)if(find(u)!=find(v)&&ty[v]!=2){
                if(!ty[v]){
                    Pre[v]=u,ty[v]=2;
                    if(!match[v]){
                        int tmp;
                        do{
                            tmp=v,match[v]=u;
                            v=match[u],match[u]=tmp;
                            u=Pre[v];
                        }while(u);
                        return true;
                    }q[++t]=match[v],ty[match[v]]=1;
                }else{
                    int lca=LCA(u,v);
                    shrink(u,v,lca),shrink(v,u,lca);
                }
            }
        }return false;
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        n=read(),m=read();
        fp(i,1,m)u=read(),v=read(),add(u,v),add(v,u);
        fp(i,1,n)res+=(!match[i]&&path(i));
        printf("%d\n",res);
        fp(i,1,n)printf("%d ",match[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10212275.html

[Link 1]: http://uoj.ac/problem/79