UVALive-3989 Ladies' Choice （稳定婚姻问题）

# 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;
}