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