HDU3081-并查集+最大二分匹配

电玩女神 2022-07-12 07:24 115阅读 0赞

# Marriage Match II #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3819    Accepted Submission(s): 1250**

Problem Description

Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of playing house we used to play when we are kids. What a happy time as so many friends playing together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.   
Now, there are 2n kids, n boys numbered from 1 to n, and n girls numbered from 1 to n. you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl X can also choose boy Z to be her boyfriend when her friend, girl Y has not quarreled with him. Furthermore, the friendship is mutual, which means a and c are friends provided that a and b are friends and b and c are friend.   
Once every girl finds their boyfriends they will start a new round of this game—marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on.  
Now, here is the question for you, how many rounds can these 2n kids totally play this game?

Input

There are several test cases. First is a integer T, means the number of test cases.   
Each test case starts with three integer n, m and f in a line (3<=n<=100,0<m<n\*n,0<=f<n). n means there are 2\*n children, n girls(number from 1 to n) and n boys(number from 1 to n).  
Then m lines follow. Each line contains two numbers a and b, means girl a and boy b had never quarreled with each other.   
Then f lines follow. Each line contains two numbers c and d, means girl c and girl d are good friends.

Output

For each case, output a number in one line. The maximal number of Marriage Match the children can play.

Sample Input

1
    4 5 2
    1 1
    2 3
    3 2
    4 2
    4 4
    1 4
    2 3

Sample Output

**题目大意**：

给你n个男的n个女的，然后给你m中关系用a b来表示，表示女a愿意和男b结婚，然后给你k种关系用a b 表示，表示女a和女b是好朋友，如果a是b的朋友，那么a也愿意和b喜欢的男的结婚，b也愿意和a喜欢的男的结婚，然后所有女进行婚配，再拆散再一次进行婚配，这一次每个女的不能选之前选过的男的，问你最多可以进行多少轮婚配使得所有女的都能选到男的

**题目思路：**

首先我们考虑朋友之间的可以相互喜欢，所以我们很好想到用并查集来处理朋友的集合，然后再一次进行建图，对于最多进行的次数，我们可以循环进行二分匹配，每次匹配后把匹配的边删掉，然后在进行匹配，依次进行

**AC代码：**

#include<cstring>
    #include<cstdio>
    
    const int maxn = 105;
    
    int link[maxn],pre[maxn];
    bool vis[maxn],mp[maxn][maxn];
    int n,m,k;
    
    
    int get(int x){              //并查集处理朋友的集合
        if(pre[x]==-1)pre[x]=x;
        if(x!=pre[x]){
            pre[x]=get(pre[x]);
        }
        return pre[x];
    }
    
    void unio(int x,int y){
        if(x!=y)pre[x]=y;
    }
    
    bool dfs(int u){
        for(int i=1;i<=n;i++){
            if(!vis[i]&&mp[u][i]){
                vis[i]=true;
                if(link[i]==-1||dfs(link[i])){
                    link[i]=u;
                    return true;
                }
            }
        }
        return false;
    }
    
    void sove(){
        int ans = 0,num;
        do{
            memset(link,-1,sizeof(link));
            num = 0;
            for(int i=1;i<=n;i++){
                memset(vis,false,sizeof(vis));
                if(dfs(i))num++;
            }
            for(int i=1;i<=n;i++){
                if(link[i]!=-1){
                    mp[link[i]][i]=false;     //将每次匹配的边删掉
                }
            }
            if(num==n)ans++;
        }while(num==n);               // 最大匹配为n说明每个女的都匹配到了
        printf("%d\n",ans);
    }
    
    int main()
    {
        int t;scanf("%d",&t);
        while(t--){
            scanf("%d%d%d",&n,&m,&k);
            memset(mp,false,sizeof(mp));
            memset(pre,-1,sizeof(pre));
            while(m--){
                int a,b;scanf("%d%d",&a,&b);
                mp[a][b]=true;
            }
            while(k--){
                int u,v;scanf("%d%d",&u,&v);
                unio(get(u),get(v));
            }
            for(int i=1;i<=n;i++){
                int x = get(i);
                for(int j=1;j<=n;j++){
                    if(get(j)==x&&j!=i){
                        for(int k=1;k<=n;k++){
                            if(mp[j][k])mp[i][k]=true;   //朋友之间的相互连边
                        }
                    }
                }
            }
            sove();
        }
        return 0;
    }