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.
题目大意：就是稳定婚姻问题，要求男士最优
思路：直接套用Gale-Shapley算法即可
PS：直接用数字不就好了吗非要用字符……
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
using namespace std; const int MAXN = ; int pref[MAXN][MAXN], order[MAXN][MAXN], next[MAXN];
int future_husband[MAXN], future_wife[MAXN];
queue<int> que;
map<char, int> mp; void engage(int man, int woman){
int &m = future_husband[woman];
if(m){
future_wife[m] = ;
que.push(m);
}
future_husband[woman] = man;
future_wife[man] = woman;
} int n, T; void GaleShapley(){
while(!que.empty()){
int man = que.front(); que.pop();
int woman = pref[man][next[man]++];
if(!future_husband[woman] || order[woman][man] < order[woman][future_husband[woman]])
engage(man, woman);
else que.push(man);
}
for(char c = 'a'; c <= 'z'; ++c) if(mp[c])
printf("%c %c\n", c, future_wife[mp[c]] + 'A' - );
} int main(){
char s[MAXN], c[];
scanf("%d", &T);
while(T--){
if(!que.empty()) que.pop();
mp.clear();
memset(pref,,sizeof(pref));
memset(order,,sizeof(order));
memset(future_husband,,sizeof(future_husband));
memset(future_wife,,sizeof(future_wife));
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%s", c), mp[c[]] = i;
for(int i = ; i <= n; ++i) scanf("%s", c), mp[c[]] = i;
for(int i = ; i < n; ++i){
scanf("%s", s);
for(int j = ; s[j]; ++j) pref[mp[s[]]][j-] = mp[s[j]];
next[mp[s[]]] = ;
que.push(mp[s[]]);
}
for(int i = ; i < n; ++i){
scanf("%s", s);
for(int j = ; s[j]; ++j) order[mp[s[]]][mp[s[j]]] = j-;
}
GaleShapley();
if(T) printf("\n");
}
}
16MS