P1682 过家家 题解

· · 题解

根据题目，由于女生之间的朋友关系可以相互传递，考虑并查集。

之后首先想到的操作就是对于输入的每一对女生关系，用并查集将女生划分为若干连通块。

然后发现对于一个连通块及与其相连的男生，在该连通块内最多进行的游戏轮数即连接的男生数目，所以应在加入男生时同步记录当前与连通块相连的男生数 cnt，而为了避免重复，引入数组 vis(i,j) 标记男生j是否已经在以第i个女生为父亲节点的连通块中。

最后遍历每个连通块，得到最小的 cnt 即为答案 ans。

由于每个女生可以强制选择 k 个男生进行游戏，故在其余连通块中的男生足够多的情况下可以进行 ans+k 轮游戏，而由于最多只能进行 n 轮游戏，需要特判，即 ans=min(ans+k,n)。

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f; 
}
const int N=300;
int n,m,k,ff;
int x[N*N],y[N*N];
int f[N],cnt[N];
bool vis[N][N];
inline int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);     
}
signed main(){
    n=read(),m=read(),k=read(),ff=read();
    for(register int i=1;i<=n;i++) f[i]=i;
    for(register int i=1;i<=m;i++) x[i]=read(),y[i]=read();
    for(register int i=1;i<=ff;i++){
        int x=read(),y=read();
        f[getf(x)]=getf(y);//合并连通块 
    }
    for(register int i=1;i<=m;i++){
        int fx=getf(x[i]);
        if(vis[fx][y[i]]) continue;
        vis[fx][y[i]]=1,cnt[fx]++;
    }
    int ans=1e9;
    for(register int i=1;i<=n;i++) ans=min(cnt[getf(i)],ans);//对每个父亲节点进行统计 
    printf("%d",min(ans+k,n));
    return 0;
}

求通过！！！