poj 3487 & hdu 1914 안정 적 인 결혼 문제 안정 적 인 결혼 시스템

//n   ,n     
//n               
//n               
//                         
//A a  ，B b  ，  A   b  a  b    A  B
//  A b     
//①     Gale-Shapley  
//                                ；
//②                         ，       
//         ，           ，      ；       ，     。
//③          ，       。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 100 ;
bool single[maxn] ; //       
int  F[maxn][maxn] ;
int  match[maxn] ;   //match[i]   i           
int num[maxn] ;   //   i          
int pos[maxn][maxn] ;
char str[maxn] ;int id[maxn] ;int idm[maxn] ;
char s[maxn] ; int n ;
int marri[maxn] ; //marri[i]    i             
int main()
{
    //freopen("in.txt" ,"r" , stdin) ;
    int T;
    int cas = 0 ;
    scanf("%d" , &T) ;
    while(T--)
    {
       scanf("%d" ,&n) ;
       memset(match , -1 , sizeof(match)) ;
       memset(id , 0 ,sizeof(id)) ;
       memset(idm , 0 , sizeof(idm)) ;
       for(int i = 1;i <= n;i++)
       single[i] = true ,num[i] = 1;
       char ch[10] ;
       for(int i = 1;i <= 2*n;i++)
       {
           scanf("%s" ,  ch) ;
           str[i] = ch[0] ;
           if(i <= n)
           id[str[i]-'a'] = i ;//             
           else
           idm[str[i]-'A'] = i - n;//             
       }
       for(int i = 1;i <= 2*n ; i++)
       {
           scanf("%s" , s) ;
           for(int j = 1;j <= n;j++)
              if(i <= n)
                 F[id[s[0]-'a']][j] = idm[s[j+1]-'A'];//F[i][j]     i     j         
              else
                  pos[idm[s[0]-'A']][id[s[j+1]-'a']] = j ;//p[i][j]   j     i       
       }   
       while(1)
       {
           int flag = 0 ;
           for(int i = 1;i <= n;i++)
           {
               if(!single[i])continue ;
                int m = F[i][num[i]] ;  // i          
                if(match[m] == -1)      //          ，      
                {
                    single[i] = false ;  
                    match[m] = i ;
                }
                else
                {
                    if(pos[m][match[m]] > pos[m][i])//                                  
                    {                               //            ，         
                        single[i] = false ;       //       
                        single[match[m]] = true ;//            
                        num[match[m]]++;        //                
                        match[m] = i ;
                    }
                    else num[i]++ ;          //           
                    flag = 1 ;           //            ，       
                }
            }
            if(!flag)
            break;
       }
       for(int i = 1;i <= n;i++)
       marri[match[i]] = i ;
       if(cas)
       puts("") ;
       for(int i = 0;i <= 26;i++)
       if(id[i])
       printf("%c %c
" , i + 'a' , str[marri[id[i]]+n]) ;
       cas = 1;
    }
}