题解 P1682 【过家家】

· · 题解

这题其实并不难，也可以不用到网络流相关知识（当然，网络流是一种更通用的方法）。

考虑到点之间存在这两种关系

  1. 男生和女生之间，可以在一起
  2. 女生和女生之间，是朋友

我们对这两种关系分别建图。

易得，由于题目朋友关系的传递性，我们可以用Floyd或并查集预处理好这些“小团体”。

对于一个小团体内部，可以共享男生。易得如果女生这边只存在这个小团体，游戏进行的次数等于这个小团体共同能够连接的男生个数。

我们处理出所有小团体单独能进行的游戏次数，全局取min即可。

注意到我们还没有考虑k，易得k直接与前面的答案累加再与n取min即可，因为只要这个数小于n，给一次强行连接的机会，一定能把游戏延长一回合。

还是放一下代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 255;

int n,m,k,f;
bool g[maxn][maxn];
bool g2[maxn][maxn]; 
int x,y;
bool vis[maxn];
bool que[maxn];
int numa,numb;
int kokona = 0x3f3f3f3f;

int get_ans(int numa,int numb){
    return numa;
}

void floyed(){
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if(g2[i][k] & g2[k][j])g2[i][j] = true;
            }
        }
    }
}
int main(){
    cin>>n>>m>>k>>f;
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        g[x][y] = true;
    }
    for (int i=1;i<=f;i++){
        cin>>x>>y;
        g2[x][y] = true;
        g2[y][x] = true;
    }
    for (int i=1;i<=n;i++)g2[i][i]=true;
    floyed();
    for (int i=1;i<=n;i++){
        if(vis[i])continue;
        for (int i=1;i<=n;i++)que[i]=false;
        numa=numb=0;
        for (int j=1;j<=n;j++){
            if(g2[i][j]){
                vis[j] = true;
                numb++;
                for (int k=1;k<=n;k++){
                    if(g[j][k]){
                        if(!que[k]){
                            que[k] = true;
                            numa++;
                        }
                    }
                }
            }
        }
        kokona = min(kokona,get_ans(numa,numb));
    }
    cout<<min(kokona+k,n)<<endl;
    return 0;
}