这题写的一把辛酸泪，第一次用getchar()读入，再加上很少用scanf()读入字符，被输入输出缓冲安排的明明白白，最后放弃治疗，用cin，还是死活没有输出，最后才发现是因为for循环多加了一步，白被坑了有一天。
算法分析：首先把每个男士加入队列，让每一个没配对的男士去向女士请求配对，如果女士没有配偶，直接答应，如果有配偶，就将配偶的优先级和当前男士的优先级作比较，如果更喜欢当前的男士，就把配偶踢掉，重新和这个男士配对，被踢掉的男士重新加入队列。
因为题目要求是有利于男士的配对，这样配对可以保证男士的配偶都是能找到的最好的，女士的是能找到最差的。
如果想有利于女士的配对，直接把主动的换成女士就好。
总而言之，就是主动者得利。
具体证明可看这个博文：http://blog.sina.com.cn/s/blog_8897e5420101bdr4.html
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int a[30],b[30],m_like[30][30],w_like[30][30],now[30],wife[30],husband[30]; 5 queue<int> q; 6 void engage(int man,int woman){ 7 int tmp=husband[woman]; 8 if(tmp!=-1){ 9 q.push(tmp); 10 wife[tmp]=-1; 11 } 12 husband[woman]=man; 13 wife[man]=woman; 14 } 15 int main() 16 { 17 int t; 18 cin>>t; 19 int T=t; 20 while(t--) 21 {if(T!=t+1) cout<<endl; 22 int n;cin>>n; 23 memset(a,0,sizeof(a)); 24 memset(b,0,sizeof(b)); 25 char x; 26 for(int i=1;i<=n;i++){ 27 cin>>x; 28 a[x-'a']=1;//按字典序输出，最后输出是从小到到遍历，如果有就输出，没有就不输出 29 } 30 for(int i=1;i<=n;i++){ 31 cin>>x; 32 b[x-'A']=1; 33 } 34 for(int i=0;i<n;i++){ 35 string s;cin>>s; 36 char ch=s[0],c;//s[0]是男士，s[1]是冒号，女士从s[2]开始 37 for(int j=2;j<n+2;j++) { 38 c=s[j]; 39 m_like[ch-'a'][j]=c-'A'; 40 }//将男士加入队列，now数组标记男士配对到第几个女士了，注意j从2开始，所以now数组也从2开始 41 q.push(ch-'a');now[ch-'a']=2,wife[ch-'a']=-1; 42 } 43 for(int i=0;i<n;i++){ 44 string s;cin>>s; 45 char ch=s[0],c; 46 for(int j=2;j<n+2;j++){ 47 c=s[j]; 48 w_like[ch-'A'][c-'a']=j; 49 } husband[ch-'A']=-1; 50 } 51 while(!q.empty()){ 52 int man=q.front();q.pop(); 53 int woman=m_like[man][now[man]++]; 54 //如果女士没有配偶，直接答应，如果有配偶，就将配偶的优先级和当前男士的优先级作比较，如果更喜欢当前的男士，重新配对 55 if(husband[woman]==-1||(w_like[woman][husband[woman]]>w_like[woman][man])) engage(man,woman); 56 else q.push(man); 57 } 58 for(int i=0;i<n;i++){ 59 if(a[i]) cout<<char(i+'a')<<" "<<char(wife[i]+'A')<<endl; 60 } 61 } 62 }