Marriage is Stable
Time Limit: 5 Seconds Memory Limit: 32768 KB Special Judge
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
這題就是穩定婚姻系統，
注意有同名的男女。
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define MAXN (2000+10)
int n;
queue<int> q;
map<string,int> hpos_male,hpos_female;
int female_like[MAXN][MAXN]; //SIS
int male_like[MAXN][MAXN]; //SSI
int match[MAXN];
string a[MAXN];
int main()
{
// freopen("zoj1576.in","r",stdin);
while (scanf("%d",&n)!=EOF)
{
hpos_male.clear();
hpos_female.clear();
memset(match,0,sizeof(match));
int size=n+1;
for (int i=1;i<=n;i++)
{
cin>>a[i];hpos_male[a[i]]=i; q.push(i);
for (int j=1;j<=n;j++)
{
string s;
cin>>s;
if (i==1)
{
hpos_female[s]=size;
a[size]=s;
size++;
}
male_like[i][j]=hpos_female[s];
}
}
for (int i=n+1;i<=2*n;i++)
{
string sg;
cin>>sg;
for (int j=1;j<=n;j++)
{
string s;
cin>>s;
female_like[hpos_female[sg]][hpos_male[s]]=j;
}
}
/*
for (int i=n+1;i<=2*n;i++)
{
for (int j=1;j<=n;j++)
cout<<female_like[make_pair(a[i],a[j])]<<' ';
cout<<endl;
}
*/
while (!q.empty())
{
int now=q.front();
q.pop();
for (int j=1;j<=n;j++)
{
int v=male_like[now][j];
if (!match[v])
{
match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
break;
}
else if (female_like[v][match[v]]>female_like[v][now])
{
q.push(match[v]);
match[match[v]]=0;
match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
break;
}
}
} www.2cto.com
for (int i=1;i<=n;i++)
{
cout<<a[i]<<' '<<a[match[i]]<<endl;
}
printf("\n");
}
return 0;
}
