Marriage is Stable （稳定婚姻匹配GS算法）

Marriage is Stable

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 75 Accepted Submission(s): 47

Problem Description Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn't necesarily mean Laura likes him. Laura likes Chuck more than Albert. So if Albert can't marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy. For the boys: Albert: Laura > Nancy > Marcy Brad: Marcy > Nancy > Laura Chuck: Laura > Marcy > Nancy For the girls: Laura: Chuck > Albert > Brad Marcy: Albert > Chuck > Brad Nancy: Brad > Albert > Chuck But if they were matched randomly, such as Albert <-> Laura  Brad <-> Marcy Chuck <-> Nancy they would soon discover it's not a nice solution. For Laura, she likes Chuck instead of Albert. And what's more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy. Now it's your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G]）and rank(M, G) < rank(M, m[M]).

Input Each case starts with an integer n (1 <= n <= 500), the number of matches to make. The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls. The following n lines are the same information for the girls. Process to the end of file.

Output             If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise. Print a blank line after each test.

Sample Input 3 Albert Laura Nancy Marcy Brad Marcy Nancy Laura Chuck Laura Marcy Nancy Laura Chuck Albert Brad Marcy Albert Chuck Brad Nancy Brad Albert Chuck

Sample Output Albert Nancy Brad Marcy Chuck Laura   白书上讲的挺好的。。。用的他的算法。。用std::map<string, int> && string[]来对名字进行储存  #include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> #include <map> #include <cmath> #include <queue> using namespace std; const int maxn = 550;// 于关键词next冲突 int n, pref[maxn][maxn], order[maxn][maxn], nex[maxn]; int future_husband[maxn], future_wife[maxn]; map<string, int> map_man, map_woman;//hash存放名字-->序列 string man[maxn], woman[maxn]; queue<int> que;//交配的队列 void engage(int man, int woman) {// int m = future_husband[woman]; if (m) {//女士有现任未婚夫 future_wife[m] = 0;//给他戴绿帽。。 que.push(m); } future_husband[woman] = man; future_wife[man] = woman; } int main() { //freopen("in.txt", "r", stdin); while (cin >> n) { map_man.clear(); map_woman.clear(); string str, name; int pos = 1; int temp; for (int i = 1; i <= n; ++i) { cin >> name; map_man[name] = i;//位置 man[i] = name;//第i个男士的姓名 nex[i] = 1;//第i个男的接下来向排名1的女士求婚 future_wife[i] = 0;//没有未婚妻 for (int j = 1; j <= n; ++j) { cin >> str; temp = map_woman[str]; if (!temp) {//这个woman还没有存到map中 map_woman[str] = temp = pos++; } woman[temp] = str; pref[i][j] = temp; } que.push(i);//将男士加入队列 } for (int i = 1; i <= n; ++i) { cin >> name; pos = map_woman[name]; future_husband[pos] = 0;//没有未婚夫 for (int j = 1; j <= n; ++j) { cin >> str; temp = map_man[str]; order[pos][temp] = j; //cout << pos << " " <<temp << endl; } } while (!que.empty()) { int man = que.front(); que.pop(); int woman = pref[man][nex[man]++];//++是为了下一个求婚对象 //cout << ::woman[woman] << " "<< order[woman][man] << " " << order[woman][future_husband[woman]] << endl; if (!future_husband[woman]) { engage(man, woman);//这个女士没有对象 } else if (order[woman][man] < order[woman][future_husband[woman]]) { engage(man, woman);//man比woman现任的未婚夫优先级高，则戴绿帽 } else { que.push(man); //这个男的继续单身 } } while (!que.empty()) que.pop(); for (int i = 1; i <= n; ++i) { cout << man[i] << " " << woman[future_wife[i]] << endl; } } }