题解 P1682 【过家家】

· · 题解

楼下提到过可以用并查集来做,所以我来贡献一篇并查集的题解
用并查集基本上就是线性时间复杂度,而且代码少,也比较好理解
这道题我们男生和女生的关系与女生和女生之间的关系分开建图
最后大概能得到这么一副关系图

女生之间会形成几个联通快
同一个联通快中的任何一个女生都能选择连接到这个联通快的男生
例如最左边的那个联通快,因为每个女生每次选择不同的男生
可以看出每个女生都有三种选择,因而游戏进行三轮
同理右边那个最多进行两轮
而中间那个孤立的点一轮都无法进行
但是题目中又说 每一个女生最多能强制k个男生接受
例如当k=2时候

游戏就能多进行两轮,那么这个孤立的点也能进行两轮游戏了
我们在计算答案的时候,先不考虑k,得到每个联通快能进行的游戏轮数
然后再取最小值,记为ans.
那么考虑k之后的最终答案就是min(ans+k,n)
具体代码如下,短小精悍 

#include<iostream>
#include<cstring>
#define MAXN 100000
using namespace std;
int n,m,k,f,pre[MAXN],num[MAXN],ans=2147483647;
bool maps[500][500]; 
struct node{int from,to;
}edge1[MAXN],edge2[MAXN];
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);} 
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)pre[fx]=fy;
}
int main()
{
    cin>>n>>m>>k>>f;
    for(int i=1;i<=n;i++)pre[i]=i;
    for(int i=1;i<=m;i++)cin>>edge1[i].from>>edge1[i].to; //女from 和 男to 从不吵架 
    for(int i=1;i<=f;i++)cin>>edge2[i].from>>edge2[i].to;  //女from 和 女to 是朋友 
    for(int i=1;i<=f;i++)merge(edge2[i].from,edge2[i].to);//朋友关系用并查集处理联通情况 
    for(int i=1;i<=m;i++)
        if(!maps[find(edge1[i].from)][edge1[i].to])       //要记录每个联通快连接的不同编号的男生数目,用maps标记防止重复计数 
            num[find(edge1[i].from)]++,  //记录每个联通快的共享男生数目
            maps[find(edge1[i].from)][edge1[i].to]=true;
    for(int i=1;i<=n;i++)
        if(num[i])ans=min(ans,num[i]); //取最小 
    ans=min(ans+k,n);  //考虑k之后的答案,最大值有可能会超过n,这显然是不行的 
    cout<<ans<<endl;
}