poj 3487（稳定婚姻问题）

参见：http://www.cnblogs.com/acSzz/archive/2012/10/17/2728461.html
View Code
  1 // File Name: 3487.cpp
  2 // Author: Missa
  3 // Created Time: 2013/2/8 星期五 10:43:21
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 using namespace std;
 17 
 18 const int maxn = 50;
 19 int male[maxn],female[maxn];
 20 vector<int>m[maxn];
 21 vector<int>fe[maxn];
 22 vector<int>inp;
 23 int f[maxn];
 24 int n;
 25 
 26 int main()
 27 {
 28     int t;
 29     scanf("%d",&t);
 30     while(t--)
 31     {
 32         scanf("%d",&n);
 33         getchar();
 34         for(int i=0;i<maxn;i++)
 35         {
 36             m[i].clear();
 37             fe[i].clear();
 38         }
 39         inp.clear();
 40         memset(male,-1,sizeof(male));
 41         memset(female,-1,sizeof(female));
 42         memset(f,0,sizeof(f));
 43         char s[maxn<<1];
 44         gets(s);
 45         for(int i=0;i<2*n;i++)
 46         {
 47             gets(s);
 48             //cout<<n<<" "<<s<<endl;
 49             int len=strlen(s);
 50             if(i<n)
 51             {
 52                 male[s[0]-'a'+1]=0;
 53                 inp.push_back(s[0]-'a'+1);
 54             }
 55             else
 56                 female[s[0]-'A'+1]=0;
 57             for(int j=2;j<len;j++)
 58             {
 59                 if(i<n)
 60                     m[s[0]-'a'+1].push_back(s[j]-'A'+1);
 61                 else
 62                     fe[s[0]-'A'+1].push_back(s[j]-'a'+1);
 63             }
 64         }
 65         while(1)
 66         {
 67             int tag=-1;
 68             for(int i=0;i<maxn;i++)
 69             {
 70                 if(male[i]==0)
 71                 {
 72                     tag=i;
 73                     break;
 74                 }
 75             }
 76             //cout<<char(tag+'a'-1)<<endl;
 77             if(tag==-1) break;
 78             while(f[tag]<m[tag].size())
 79             {
 80                 int t=m[tag][f[tag]];
 81                 //cout<<endl;
 82                 //cout<<tag<<" "<<f[tag]<<" "<<t<<" "<<female[t]<<endl;
 83                 f[tag]++;
 84                 int flag=0;
 85                 if(female[t]==0)
 86                 {
 87                     male[tag]=t;
 88                     female[t]=tag;
 89                     break;
 90                 }
 91                 else if(female[t]>0)
 92                 {
 93                     int tt=female[t];
 94                     for(int k=0;k<fe[t].size();k++)
 95                     {
 96                         if(fe[t][k]==tag)
 97                         {
 98                     //        cout<<t<<endl;
 99                             male[tag]=t;
100                             female[t]=tag;
101                             male[tt]=0;
102                             flag=1;
103                             break;
104                         }
105                         if(fe[t][k]==tt)
106                         {
107                             flag=1;
108                             break;
109                         }
110                     }
111                 }
112                 if(flag) break;
113                 //cout<<char(tag+'a'-1)<<endl;
114             }
115         }
116         for(int i=0;i<n;i++)
117             printf("%c %c\n",inp[i]+'a'-1,male[inp[i]]+'A'-1);
118         printf("\n");
119     }
120     return 0;
121 }