acm专题5——稳定婚配问题

稳定婚配问题"/>

acm专题5——稳定婚配问题

模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int MAXN=505;
int n,bf,gf;
map<int,string>b;
map<int,string>g;
map<string,int>b1;
map<string,int>g1;
int rank1[MAXN];
int match_boy[MAXN],match_girl[MAXN];//match_boy[i]编号为i的男士配对的女士
int boy[MAXN][MAXN],girl[MAXN][MAXN];//boy[i][j] 第i个男的的第j个喜欢的女的的编号,girl[i][j]在编号为i的女士心中，编号为j的男士的排名
void init()
{memset(match_boy,0,sizeof(match_boy));memset(match_girl,0,sizeof(match_girl));memset(rank1,0,sizeof(rank1));b.clear();g.clear();b1.clear();g1.clear();bf=gf=0;
}
void match()
{int flag=1;while(flag){flag=0;for(int i=1;i<=n;i++){if(match_boy[i]==0){int temp=boy[i][++rank1[i]];if(match_girl[temp]==0)match_boy[i]=temp,match_girl[temp]=i;else if(girl[temp][i]<girl[temp][match_girl[temp]] ){match_boy[match_girl[temp]]=0;match_boy[i]=temp;match_girl[temp]=i;}flag=1;}}}
}
char name[MAXN];
string na;
void solve()
{while(~scanf("%d",&n))
{for(int i=1;i<=n;i++){scanf("%s",name);na=string(name);b[++bf]=na;b1[na]=bf;for(int j=1;j<=n;j++){scanf("%s",name);na=string(name);if(i==1)g[++gf]=na,g1[na]=gf;boy[i][j]=g1[na];}}for(int i=1;i<=n;i++){scanf("%s",name);na=string(name);int gn=g1[na];for(int j=1;j<=n;j++){scanf("%s",name);na=string(name);girl[gn][b1[na]]=j;}}match();for(int i=1;i<=n;i++)cout<<b[i]<<' '<<g[match_boy[i]]<<endl;puts("");init();
}return;
}
int main()
{
/*ll T;scanf("%lld",&T);while(T--)
*/solve();return 0;
}