BZOJ 1854: [Scoi2010]游戏（二分图匹配/并查集）

题面：

　　https://www.lydsy.com/JudgeOnline/problem.php?id=1854

题解：

　　1.二分图匹配：

　　　　首先我们发现每件装备只能在两种属性中选一种。因此，我们以每个装备的编号向两种属性分别连边。然后用1-n的属性分别进行向装备的匹配，一旦有一种匹配不上就退出。

　　　　代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int head[maxn],vis[maxn],fa[maxn],ans,cnt,n,maxx;

struct ed{

    int next,to;

}e[maxn<<];

void add(int u,int v){

    e[++cnt]=(ed){head[u],v};

    head[u]=cnt;

}

bool hungary(int now,int sign){

    for(int i=head[now];i;i=e[i].next){

        int tt=e[i].to;

        if(vis[tt]==sign) continue;

        vis[tt]=sign;

        if(!fa[tt]||hungary(fa[tt],sign)){

            fa[tt]=now;

            return ;

        }

    }

    return ;

}

int main(){

    scanf("%d",&n);

    int u,v;

    for(int i=;i<=n;i++){

        scanf("%d%d",&u,&v);

        add(u,i),add(v,i);

        maxx=max(maxx,max(u,v));

    }

    for(int i=;i<=maxx;i++){

        if(!hungary(i,i))

            break;

        ans++;

    }

    printf("%d",ans);

    return ;

}

　　　2.并查集：　

　　　　同样的，每种装备的两个属性只能选一个，那么，我们可以将每一种装备看做一条将两种属性相连的边。很显然，这些属性被分成了一个个的联通块。那么不难发现，只有当一个联通块内有环时，这个联通块才能每个属性都被选中，否则（即为一棵树）必须有一个不选，显然不选编号最大的最优。又因为每个点在且仅在一个联通块（单独的一个点也算一个联通块），所以这就满足了并查集的要求。

　　　　代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int fa[maxn],val[maxn],ans,n;

int ffa(int x){

    return fa[x]==x?x:fa[x]=ffa(fa[x]);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        fa[i]=i;

    int u,v;

    for(int i=;i<=n;i++){

        scanf("%d%d",&u,&v);

        int fu=ffa(u),fv=ffa(v);

        if(fu==fv)

            val[fu]++;

        else{

            fa[fv]=fu;val[fu]++;

            val[fu]+=val[fv];

            val[fv]=;

        }

    }

    for(int i=;i<=n;i++)

        if(val[ffa(i)])

            ans++,val[ffa(i)]--;

        else break;

    printf("%d",ans);

    return ;

}

算法比较：

　　　　上面是二分图匹配，下面是并查集

巴特西

BZOJ 1854: [Scoi2010]游戏（二分图匹配/并查集）

最新文章

热门文章