2019-02-25-The Stable Marriage Problem-POJ3487-穩定婚姻算法

POJ-3487-The Stable Marriage Problem

Problem Description

The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of:

a set M of n males;

a set F of n females;

for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least).

A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers f over his current partner. The stable marriage A is called male-optimal if there is no other stable marriage B, where any male matches a female he prefers more than the one assigned in A.

Given preferable lists of males and females, you must find the male-optimal stable marriage.

Input

The first line gives you the number of tests. The first line of each test case contains integer n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter, female name is an upper-case letter. Then go n lines, that describe preferable lists for males. Next n lines describe preferable lists for females.

Output

For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases.

Sample Input

2

3

a b c A B C

a:BAC

b:BAC

c:ACB

A:acb

B:bac

C:cab

3

a b c A B C

a:ABC

b:ABC

c:BCA

A:bac

B:acb

C:abc

Sample Output

a A

b B

c C

a B

b A

c C

題目簡述

對于給定的n對男女，再給出相應的好感度排名，即男生眼中女生的好感度排名(n行)和女生眼中男生的好感度排名(n行)。

對于兩個比對a-b，c-d，如果a的眼中d的排名比b高，d的眼中a排名比c高，那麼這樣的比對不穩定。

試求出一種比對方式，使得對于所有的男生和女生，都是一個穩定的比對。

條目檢索：穩定婚姻算法

輸入輸出

輸入：無難點，字元串讀入即可

輸出：無難點

使用模闆（Gale_Shapley穩定婚姻算法）

struct Gale_Shapley{
	static const int N=60;
	int n;
	int fg;
	int woman[N][N];        //第i個girl對編号j的boy的好感排位 
	int man[N][N];          //第i個boy第j喜歡的girl 
	int man_match[N],woman_match[N];    //已比對的男女 
	int p[N];               //第i個boy已經表白的人數 
	void solve(){
		for(int i=0;i<N;i++)p[i]=1;
		memset(man_match,0,sizeof(man_match));
		memset(woman_match,0,sizeof(woman_match));
		fg=true;
		while(fg){
			fg=false;
			for(int i=1;i<=n;i++){
				if(!man_match[i]){
					int t=man[i][p[i]++];
					if(!woman_match[t]){
						man_match[i]=t;
						woman_match[t]=i;
					}else if(woman[t][woman_match[t]]>woman[t][i]){
						man_match[woman_match[t]]=0;
						man_match[i]=t;
						woman_match[t]=i;
					}
					fg=true;
				}
			}
		}
	}
}T;
           

AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
//使用模闆
struct Gale_Shapley{
	static const int N=60;
	int n;
	int fg;
	int woman[N][N];//第i個girl對編号j的boy的好感排位 
	int man[N][N];//第i個boy第j喜歡的girl 
	int man_match[N],woman_match[N];//已比對的男女 
	int p[N];//第i個boy已經表白的人數 
	void solve(){
		for(int i=0;i<N;i++)p[i]=1;
		memset(man_match,0,sizeof(man_match));
		memset(woman_match,0,sizeof(woman_match));
		fg=true;
		while(fg){
			fg=false;
			for(int i=1;i<=n;i++){
				if(!man_match[i]){
					int t=man[i][p[i]++];
					if(!woman_match[t]){
						man_match[i]=t;
						woman_match[t]=i;
					}else if(woman[t][woman_match[t]]>woman[t][i]){
						man_match[woman_match[t]]=0;
						man_match[i]=t;
						woman_match[t]=i;
					}
					fg=true;
				}
			}
		}
	}
}T;

int main(){
	int cases;
	scanf("%d",&cases);
	while(cases--){
		scanf("%d",&T.n);
		char boy[27];         //編号對應的字母
		char girl[27];        //編号對應的字母
		char s[30];
		map<char,int>bo,gi;   //字母對應的編号
        //建立映射
		for(int i=1;i<=T.n;i++){
			scanf("%s",s);
			boy[i]=s[0];
			bo[s[0]]=i;
		}
		for(int i=1;i<=T.n;i++){
			scanf("%s",s);
			girl[i]=s[0];
			gi[s[0]]=i;
		}
        //讀入排名
		for(int i=1;i<=T.n;i++){
			scanf("%s",s);
			int x,y;
			x=bo[s[0]];
			for(int j=1;j<=T.n;j++){
				y=gi[s[1+j]];
				T.man[x][j]=y;      //男生x所第j喜歡的女生是y
			}
		}
		for(int i=1;i<=T.n;i++){
			scanf("%s",s);
			int x,y;
			x=gi[s[0]];
			for(int j=1;j<=T.n;j++){
				y=bo[s[1+j]];
				T.woman[x][y]=j;    //對于女生x而言男生y的排名是j
			}
		}

		T.solve();

		for(int i=1;i<=T.n;i++){
			printf("%c %c\n",boy[i],girl[T.man_match[i]]);
		}
		if(cases!=0)printf("\n");
	}
	return 0;
}
           

參考連結

https://blog.csdn.net/u011815404/article/details/81395124

https://blog.csdn.net/cscmaker/article/details/8291131