P1682 过家家

Xu_brezza · 2022-04-12 21:34:32 · 题解

题意：

有 n 个男生 n 个女生，编号都是 1 到 n。 男生和女生直接有不讨厌关系，那二者可以一起玩。女生和女生有朋友关系，女生的朋友的不讨厌的男生也可以和女生玩。当所有女生都找到玩伴（也可以是多对一），是一轮游戏，然后可以找其他玩伴进行下一轮，问最多进行几轮。还有就是每个女生可以强制选 k 个玩伴。

分析：

作为我自己做出来的蓝题，有点小激动。

首先这个题意之下隐藏了什么呢？显然是一个图，其中可以分为女生之间的连边和男女之间的连边。那么对于女生之间的连边，显然她们构成的连通块可以到达彼此任意相连的男生，那么对于这个连通块，我们最多可以有 cnt 次游戏，每次都是多对一，其中 cnt 为连通块向男生连出的出边数量。

再看这个强制选，其实也没啥，就是答案次数加上 k ，因为每个女生都可以再选 k 个，那不就是再进行 k 轮也就是总数加上 k 吗。

由此我们总结出算法：并查集维护女生连通块，统计女生连通块与男生连边数量，取最小值（因为所有女生都要玩），再加上 k ，还不能超过 n 因为女生最多和 n 个男生玩 n 次对吧。

管理大大求过QWQ。

#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
const int N = 255;
struct qwq{
    int u,v;
}bg[N*N],gg[N];
int fa[N],check[N][N],cnt[N],n,m,f,k;
inline int findfa(int x){return fa[x] == x ? x : fa[x] = findfa(fa[x]);}
signed main(){
    scanf("%d%d%d%d",&n,&m,&k,&f);
    for(int i=1;i<=n;++i)fa[i] = i;
    for(int i=1;i<=m;++i)scanf("%d%d",&bg[i].u,&bg[i].v);
    for(int i=1;i<=f;++i){
        scanf("%d%d",&gg[i].u,&gg[i].v);
        int x = findfa(gg[i].u),y = findfa(gg[i].v);//女生合并 
        if(x != y)fa[x] = y; 
    }
    for(int i=1;i<=m;++i){
        int x = findfa(bg[i].u),y = bg[i].v;//取出男女qwq 
        if(!check[x][y]){//统计该女生连通块连多少个男生 
            check[x][y] = 1;
            cnt[x]++;
        }
    }
    int ans = INT_MAX;
    for(int i=1;i<=n;++i)ans = cnt[i] ? min(ans,cnt[i]) : ans;
    ans += k;
    printf("%d",min(ans,n)); 
}