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=1000010;
int head[maxn],vis[maxn],fa[maxn],ans,cnt,n,maxx;

struct ed{
    int next,to;
}e[maxn<<3];

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 1;
        }
    }
    return 0;
}

int main(){
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&u,&v);
        add(u,i),add(v,i);
        maxx=max(maxx,max(u,v));
    }
    for(int i=1;i<=maxx;i++){
        if(!hungary(i,i))
            break;
        ans++;
    }
    printf("%d",ans);
    return 0;
}

 

　　　2.并查集：　

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

　　　　代码：

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxn=1000010;
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=1;i<=n;i++)
        fa[i]=i;
    int u,v;
    for(int i=1;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]=0;  
        }
    }
    for(int i=1;i<=n;i++)
        if(val[ffa(i)])
            ans++,val[ffa(i)]--;
        else break;
    printf("%d",ans);   
    return 0;   
}

算法比较：

 　　　　

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