题解 P1682 【过家家】

glorious_dream · 2022-04-12 21:07:25 · 题解

题目大意：

有 n 个男生和 n 个女生，每次女生可以选择一个不会吵架的男生来玩，且可以强制 k 个男生跟她玩，求最多能玩多少轮。

算法讲解：

首先，可以发现有合并女生的操作，可以想到用并查集来维护。

考虑两个女生是朋友，把她们用并查集加在一起，形成一个联通块。在每一个联通块内，女生可以选择任何一个男生玩。这样假设一共形成 x 个联通块，那么答案就是这 x 个联通块中的可匹配数量的最小值。

最后别忘了加上 k 与 n 比较，答案是较小的那个值。

总代码：

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x/10) print(x/10);
    putchar(x%10+'0');
}
const int M = 1e5+10;
int f[M],vis[500][500],cnt[M];
int n,m,k,t,ans=INT_MAX;
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
struct dat{
    int x,y;
}a[M];
signed main(){
    n=read(),m=read(),k=read(),t=read();
    for(re int i(1) ; i<=n ; ++i) f[i] = i;
    for(re int i(1) ; i<=m ; ++i) a[i].x=read(),a[i].y=read();
    for(re int i(1) ; i<=t ; ++i){
        int x=read(),y=read();
        int fx=find(x),fy=find(y);
        if(fx == fy) continue;
        f[fx] = fy;
    }
    for(re int i(1) ; i<=m ; ++i){
        if(!vis[find(a[i].x)][a[i].y]){
            cnt[find(a[i].x)]++;
            vis[find(a[i].x)][a[i].y]=1;
        }
    }
    for(re int i(1) ; i<=n ; ++i) if(cnt[i]) ans=min(ans,cnt[i]);
    printf("%d",min(ans+k,n));
    return 0;
}