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

2019-11-08 19:26:00

字體：大中小

供稿：網(wǎng)友

Marriage Match II

Time Limit: 2000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3819 Accepted Submission(s): 1250PRoblem DescriptionPresumably, 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? InputThere 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. OutputFor each case, output a number in one line. The maximal number of Marriage Match the children can play. Sample Input

14 5 21 12 33 24 24 41 42 3 Sample Output2 題目大意：
                  給你n個男的n個女的，然后給你m中關(guān)系用a b來表示，表示女a(chǎn)愿意和男b結(jié)婚，然后給你k種關(guān)系用a b 表示，表示女a(chǎn)和女b是好朋友，如果a是b的朋友，那么a也愿意和b喜歡的男的結(jié)婚，b也愿意和a喜歡的男的結(jié)婚，然后所有女進行婚配，再拆散再一次進行婚配，這一次每個女的不能選之前選過的男的，問你最多可以進行多少輪婚配使得所有女的都能選到男的
題目思路：
                 首先我們考慮朋友之間的可以相互喜歡，所以我們很好想到用并查集來處理朋友的集合，然后再一次進行建圖，對于最多進行的次數(shù)，我們可以循環(huán)進行二分匹配，每次匹配后把匹配的邊刪掉，然后在進行匹配，依次進行
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;}