UVALive-3989 Ladies' Choice (稳定婚姻问题)

时间:2021-02-26 10:17:27

题目大意:稳定婚姻问题。。。。

题目分析:模板题。

代码如下:

# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CL(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b) const int N=1005;
int fu_husband[N],fu_wife[N],order[N][N],pref[N][N],nxt[N],n;
queue<int>q; void engage(int man,int woman)
{
int k=fu_husband[woman];
if(k){
fu_wife[k]=0;
q.push(k);
}
fu_wife[man]=woman;
fu_husband[woman]=man;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
while(!q.empty()) q.pop();
REP(i,1,n+1){
REP(j,1,n+1) scanf("%d",&pref[i][j]);
nxt[i]=1;
fu_wife[i]=0;
q.push(i);
}
REP(i,1,n+1){
REP(j,1,n+1){
int x;
scanf("%d",&x);
order[i][x]=j;
}
fu_husband[i]=0;
}
while(!q.empty()){
int man=q.front();
q.pop();
int woman=pref[man][nxt[man]++];
if(!fu_husband[woman])
engage(man,woman);
else if(order[woman][man]<order[woman][fu_husband[woman]])
engage(man,woman);
else
q.push(man);
}
REP(i,1,n+1) printf("%d\n",fu_wife[i]);
if(T) printf("\n");
}
return 0;
}