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:abcSample Output
a A b B c C a B b Ac C
男士是小写,女士是大写
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int maxn=30; int couple;//总共多少对 int malelike[maxn][maxn],femalelike[maxn][maxn]; //男士对女士的喜欢程度(按降序排列)和女士对男士的喜欢程度 int malechoice[maxn],femalechoice[maxn];//男士和女士的选择,男士选择了第几喜欢的 int malename[maxn],femalename[maxn];//名字的hash,方便打印对应编号的名字 int main(){ int T; char str[30]; scanf("%d",&T); while(T--) { queue<int> freemale;//没有配对的男士 scanf("%d",&couple); for(int i=0;i<couple;i++) { scanf("%s",str); malename[i]=str[0]-'a'; freemale.push(malename[i]); } //将名字排序,便于字典序 sort(malename,malename+couple); for(int i=0;i<couple;i++) { //女士是大写 scanf("%s",str); femalename[i]=str[0]-'A'; } //男士对女士的印象,按降序排列 for(int i=0;i<couple;i++) { scanf("%s",str); for(int j=0;j<couple;j++) malelike[i][j]=str[j+2]-'A';//他喜欢的是谁 } //女士对男士的打分,添加虚拟人物,编号为couple,为女士的初始对象 for(int i=0;i<couple;i++) { scanf("%s",str); for(int j=0;j<couple;j++) femalelike[i][str[j+2]-'a']=couple-j;//她喜欢他多少 femalelike[i][couple]=0; } //初始化男士选自己最喜欢的女士,其实还是光棍 memset(malechoice,0,sizeof(malechoice)); //女士先初始一个对象 for(int i=0;i<couple;i++) femalechoice[i]=couple; while(!freemale.empty()) { //找出一个未配对的男士,注意不要习惯性的pop int male=freemale.front(); //男士心仪的女士 int female=malelike[male][malechoice[male]]; //如果当前的男士比原来的男友更好 if(femalelike[female][male]>femalelike[female][femalechoice[female]]) { //该男士成功脱单 freemale.pop(); //如果有前男友,则把前男友打回光棍,则该光棍只能考虑下一个女士咯 //不要把虚拟的人物加入队列,否则死讯坏或者错误 if(femalechoice[female]!=couple) { freemale.push(femalechoice[female]); malechoice[femalechoice[female]]++; } //当前男友为这位男士 femalechoice[female]=male; } //如果被该女士拒接,则只能找下一个女士咯 else malechoice[male]++; } for(int i=0;i<couple;i++) printf("%c %c\n",malename[i]+'a', malelike[malename[i]][malechoice[malename[i]]]+'A'); puts(""); } return 0; }