bzoj2184: 任意图的匹配

Description

每天都要考，每天都要讲，大家注意力都集中不起来了，每天听解题报告时都有人交头接耳（也包括我，呵呵）。这样做大大的影响的学习效率（可能吧）。于是，有些好奇心重的同学就开始研究，怎样才会最吵。培训的总共有N个人，但不是每两人之间都讲话，只有一些人有话题聊，而且一个人可能会和多个人有话题（共M对人）。如果所有同学都说在话，教室里最吵。你的任务就是求出把说话者对数控制在多少人以内，无论如何教室里不会变得最吵？注意：A和B说话，同时B和C说话，这算两对人说话。

Input

第一行两个整数N,M。接下来M行，每行两个整数x,y表示x和y有话题聊。

Output

一行，一个整数表示要把说话者对数控制在多少以内，无论如何教室里不最吵。

若有孤立点，则答案为M，否则设最少用k条边覆盖所有点，则答案为k-1

k=N-最大匹配

#include<bits/stdc++.h>

const int N=;

int es[N],enx[N],e0[N],ep,q[N],ql,qr,n,m,f[N],nx[N],pv[N],t[N],ts[N],tk=,ans=;

void ae(int a,int b){

    es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;

    es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;

}

int get(int x){return x!=f[x]?f[x]=get(f[x]):x;}

int lca(int x,int y){

    ++tk;

    while(){

        if(x){

            x=get(x);

            if(ts[x]==tk)return x;

            ts[x]=tk;

            x=pv[nx[x]];

        }

        std::swap(x,y);

    }

}

void mg(int a,int b){

    while(a!=b){

        int w=nx[a],u=pv[w];

        if(get(u)!=b)pv[u]=w;

        if(t[a]==)t[q[++qr]=a]=;

        if(t[w]==)t[q[++qr]=w]=;

        if(a==f[a])f[a]=b;

        if(w==f[w])f[w]=b;

        a=u;

    }

}

int bfs(int w0){

    for(int i=;i<=n;++i)f[i]=i,pv[i]=,t[i]=;

    ql=qr=;

    q[++qr]=w0;

    while(ql!=qr){

        int w=q[++ql];

        for(int i=e0[w];i;i=enx[i]){

            int u=es[i];

            if(u==nx[w]||get(w)==get(u)||t[u]==)continue;

            if(t[u]==){

                int v=lca(w,u);

                if(get(w)!=v)pv[w]=u;

                if(get(u)!=v)pv[u]=w;

                mg(w,v);mg(u,v);

            }else if(nx[u]){

                pv[u]=w;

                t[u]=;

                t[q[++qr]=nx[u]]=;

            }else{

                while(w){

                    int a=nx[w];

                    nx[w]=u;nx[u]=w;

                    u=a;

                    w=pv[u];

                }

                return ;

            }

        }

    }

    return ;

}

int main(){

    while(scanf("%d%d",&n,&m)==){

        memset(e0,,sizeof(int)*(n+));

        memset(nx,,sizeof(int)*(n+));

        ep=;

        for(int i=,a,b;i<=m;++i){

            scanf("%d%d",&a,&b);

            ae(a,b);

        }

        for(int i=;i<=n;++i)if(!e0[i]){

            printf("%d\n",m);

            goto o;

        }

        ans=;

        for(int i=;i<=n;++i)if(!nx[i])ans+=bfs(i);

        printf("%d\n",n-ans-);

        o:;

    }

    return ;

}

巴特西

bzoj2184: 任意图的匹配

Description

Input

Output

最新文章

热门文章