P1682 过家家

Rikka__ · 2021-08-21 09:28:15 · 题解

大家好，我非常喜欢使用 STL，所以用 Bitset 过了这个题 。

题意

对于每个女生及与其朋友节点划分为一个联通块，答案就是每个联通块相连的男生数加上可强制接受的数量的最小值 。

但是可能会出现答案的值多于男生数量的情况，所以我们要将答案和男生人数去一个最小值 。

思路

可以很容易的想到用并查集去维护女生的联通块，但是男生怎么处理 ?

于是我想到了 Bitset，这样我们可以很方便的存储与女生节点相连的男生有谁，维护与联通块相连的男生时只用将联通的女生节点的 Bitset 按位或起来就可以很快的维护答案了 。

我们可以想一想这道题使用 Bitset 的优点 ：

• 操作方便，直接将两个 Bitset 或一下就行
• 不用去重，不用判断两个女生节点可以直接接受同一个男生，因为或起来之后相同的位置不会有新增贡献。

（于是我就拿了个最优解。。

Code：

#include<bits/stdc++.h>
using namespace std;
#define _ =read()
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}
bitset<260> s[260];
int n;
int m;
int f;
int k;
int fa[260];
int find(int x){ return fa[x]==0?fa[x]=x:fa[x]==x?x:fa[x]=find(fa[x]);}
signed main(){
    n _;
    m _;
    k _;
    f _;
    for(int x,y,i=1;i<=m;++i){
        x _;
        y _;
        s[x][y]=1;
    }
    for(int i=1,x,y;i<=f;++i){
        x _;
        y _;
        int fx=find(x);
        int fy=find(y);
        s[fx]|=s[fy];
        s[fy]|=s[fx];
        if(fx!=fy) fa[fy]=fa[x];
    }
    int ans=INT_MAX;
    for(int i=1;i<=n;i++){
        s[i]|=s[find(i)];
    }

    for(int i=1;i<=n;++i) ans=min(ans,int(s[i].count()+k));
    cout<<min(ans,n);
    return 0;
}

9.11 Update：感谢 @Whitharm 提供的 hack , （ 未在最后使一个并查集内的节点的 bitset 统一 ） 已对代码进行了修改 。