PKU 3487 The Stable Marriage Problem

http://poj.org/problem?id=3487

普通の安定結婚問題のようです。
冬学期にとっていた授業で説明されたのですが、うろおぼえだったので結局ウィキペディアに頼らせていただきました。
時間制限も十分ありますし、書いたら普通に通りましたが、ソースはあまりきれいではないですね。

#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define F first
#define S second

main(){
  int T;
  cin>>T;
  rep(test,T){
    if(test)cout<<endl;

    int n;
    cin>>n;

    char M[n],F[n];
    rep(i,n)cin>>M[i];
    rep(i,n)cin>>F[i];

    map<char,map<char,int> > lis;

    rep(i,2*n){
      string ss;
      cin>>ss;
      int a=ss[0];
      rep(j,n){
	int b=ss[2+j];
	lis[a][b]=j;
      }
    }
    map<char,char> ans;//m,f
    map<char,char> sna;//f,m
    set<char> ndf;

    queue<char> Q;
    rep(i,n)Q.push(M[i]);

    while(!Q.empty()){
      int h=Q.front();Q.pop();

      int topp=100,d;
      
      FOR(miter,lis[h]){
	if(miter->S<topp){
	  topp=miter->S;
	  d=miter->F;
	}
      }

      lis[h].erase(d);
      
      if(ndf.count(d)==0){
	ndf.insert(d);
	ans[h]=d;
	sna[d]=h;
      }else{
	int hh=sna[d];
	int dtoh=lis[d][h],dtohh=lis[d][hh];
	if(dtoh>dtohh){
	  Q.push(h);
	}else{
	  Q.push(hh);
	  ans[h]=d;
	  sna[d]=h;
	}
      }
    }

    FOR(miter,ans){
      cout<<miter->F<<" "<<miter->S<<endl;
    }
  }
}