2013
12-12

# Marriage is Stable

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
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]).

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.

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.

3
Albert Laura Nancy Marcy
Chuck Laura Marcy Nancy
Nancy Brad Albert Chuck

Albert Nancy
Chuck Laura

Gale-Shapley 算法

while  存在男人m是自由的且还没对每个女人都求过婚
选择这个男人m
令w是m的优先表中还没求过婚的最高排名的女人
if  w是自由的
（m，w）变成约会状态
else  w当前与m1约会
if  w更偏爱m1而不爱m
m保持自由
else    w更偏爱m而不爱m1
（m，w）变成约会状态
m1变成自由
endif
endif
endwhile

 Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 5426960 2012-02-27 23:36:05 Accepted 1522 0MS 568K 1851 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
int n,gp_boy[505][505],gp_girl[505][505],boy[505],girl[505],rank[505];
map<string,int>mp_boy,mp_girl;
string sboy[505],sgirl[505];
char s[1000];
void deal()
{
memset(boy,0,sizeof(boy));
memset(girl,0,sizeof(girl));
for(int i=1;i<=n;i++)rank[i]=1;
while(1)
{
int flag=0;
for(int i=1;i<=n;i++)
{
if(!boy[i])
{
int g=gp_boy[i][rank[i]++];
if(!girl[g])
boy[i]=g,girl[g]=i;
else if(gp_girl[g][i]>gp_girl[g][girl[g]])
boy[girl[g]]=0,girl[g]=i,boy[i]=g;
flag=1;
}
}
if(!flag)break;
}
for(int i=1;i<=n;i++)
{
cout<<sboy[i]<<' '<<sgirl[boy[i]]<<endl;
}
puts("");
}
int main()
{
while(~scanf("%d",&n))
{
getchar();
mp_boy.clear(),mp_girl.clear();
int pos=1,tem;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
sboy[i]=s,mp_boy[s]=i;
for(int j=1;j<=n;j++)
{
scanf("%s",s);
tem=mp_girl[s];
if(tem==0)
mp_girl[s]=tem=pos++,sgirl[tem]=s;
gp_boy[i][j]=tem;
}
}
for(int i=0;i<n;i++)
{
scanf("%s",s);
int x=mp_girl[s];
for(int j=0;j<n;j++)
{
scanf("%s",s);
int y=mp_boy[s];
gp_girl[x][y]=n-j;
}
}
deal();
}
return 0;
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）