http://poj.org/problem?id=3487
题目：有N位女士和N位男士，每位男士或者女士都对对方有个评价。他们会形成N对夫妻，如果A和a结婚，B和b结婚，但是A更偏爱b而非a而且b也更偏爱A而非B，那么这种婚姻是不稳定的 ，求 一个稳定的 婚姻 配对。
题目要求是男士优先，也就是男士优先表白，肯定会从最喜欢的开始表白，如果对方没有男友或者表白的男士优于当前男友，就会抛弃原来的男友，而接受表白的男士，男士也成功脱光。否则男士会被拒绝，便只能考虑下一个喜欢的女士。直到所有人都脱光，不存在拒绝情况为止。
队列实现，将自由男一个个拿出来，寻找女士一个个进行匹配。
感觉上先表白的男士会沾光，其实肯定不然。。。。是不是只有唯一的稳定婚姻呢，觉得如果没有对两个人的评价完全相同的情况下，应该是唯一的
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-6
15 #define inf 10001000
16
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 #define inf 9999999
21 using namespace std;
22
23 const double pi = acos(-1.0);
24 const int maxn = 210;
25 #define N 30
26
27 int mlike[N][N],flike[N][N],inivite[N],mmatch[N],fmatch[N] ;
28 queue<int>que;
29 int n ;
30 void init()
31 {
32 CL(mlike,0);
33 CL(flike,0) ;
34 CL(inivite,0);
35 CL(mmatch,-1) ;
36 CL(fmatch,-1) ;
37 while(!que.empty())que.pop() ;
38
39 }
40 void GaleShapley()
41 {
42
43 while(!que.empty())
44 {
45 int now = que.front();que.pop() ;
46 inivite[now]++;
47 if(inivite[now] > n) continue ;//已经邀请过了了 所有的 女士
48
49 int fe = mlike[now][inivite[now]] ;// 当前最喜欢的女士
50
51 if(fmatch[fe] == -1)// 若女士 没有 对象
52 {
53 fmatch[fe] = now;
54 mmatch[now] = fe;
55 continue ;
56 }
57 else
58 {
59 int old = fmatch[fe] ;// 若 有对象
60 if(flike[fe][old] < flike[fe][now])// 女士 更喜欢 原先的
61 {
62 que.push(now) ;
63 continue;
64 }
65 else
66 {
67 que.push(old);// 女士 更喜欢你现在的
68 fmatch[fe] = now ;
69 mmatch[now] = fe ;
70 mmatch[old] = -1 ;
71 }
72 }
73
74 }
75 }
76 char str[100] ;
77 int main()
78 {
79 //read() ;
80 int t,i,j;
81 scanf("%d",&t);
82 while(t--)
83 {
84 init() ;
85
86 scanf("%d",&n);
87 getchar() ;
88 gets(str) ;
89
90 for(i = 1 ; i <= n;i++)
91 {
92
93 scanf("%s",str) ;
94
95 int tmp = str[0] - 'a' + 1 ;
96 que.push(tmp) ;
97 for(j = 1; j <= n ;j++)
98 {
99 mlike[tmp][j] = str[j + 1] - 'A' + 1 ;
100
101 }
102 }
103 for(i = 1; i <= n;i++)
104 {
105 scanf("%s",str);
106 int tmp = str[0] - 'A' + 1;
107 for(j = 1;j <= n;j++)
108 {
109 int a = str[j + 1] - 'a' + 1 ;
110 flike[tmp][a] = j ;
111 }
112 }
113 GaleShapley();
114
115 for(i = 1 ; i <= n;i++)
116 {
117 if(mmatch[i]!= -1)
118 {
119 printf("%c %c\n",i + 'a' - 1,mmatch[i] + 'A' -1) ;
120 }
121 }
122 printf("\n") ;
123
124
125
126
127 }
128
129 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-6
15 #define inf 10001000
16
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 #define inf 9999999
21 using namespace std;
22
23 const double pi = acos(-1.0);
24 const int maxn = 210;
25 #define N 30
26
27 int mlike[N][N],flike[N][N],inivite[N],mmatch[N],fmatch[N] ;
28 queue<int>que;
29 int n ;
30 void init()
31 {
32 CL(mlike,0);
33 CL(flike,0) ;
34 CL(inivite,0);
35 CL(mmatch,-1) ;
36 CL(fmatch,-1) ;
37 while(!que.empty())que.pop() ;
38
39 }
40 void GaleShapley()
41 {
42
43 while(!que.empty())
44 {
45 int now = que.front();que.pop() ;
46 inivite[now]++;
47 if(inivite[now] > n) continue ;//已经邀请过了了 所有的 女士
48
49 int fe = mlike[now][inivite[now]] ;// 当前最喜欢的女士
50
51 if(fmatch[fe] == -1)// 若女士 没有 对象
52 {
53 fmatch[fe] = now;
54 mmatch[now] = fe;
55 continue ;
56 }
57 else
58 {
59 int old = fmatch[fe] ;// 若 有对象
60 if(flike[fe][old] < flike[fe][now])// 女士 更喜欢 原先的
61 {
62 que.push(now) ;
63 continue;
64 }
65 else
66 {
67 que.push(old);// 女士 更喜欢你现在的
68 fmatch[fe] = now ;
69 mmatch[now] = fe ;
70 mmatch[old] = -1 ;
71 }
72 }
73
74 }
75 }
76 char str[100] ;
77 int main()
78 {
79 //read() ;
80 int t,i,j;
81 scanf("%d",&t);
82 while(t--)
83 {
84 init() ;
85
86 scanf("%d",&n);
87 getchar() ;
88 gets(str) ;
89
90 for(i = 1 ; i <= n;i++)
91 {
92
93 scanf("%s",str) ;
94
95 int tmp = str[0] - 'a' + 1 ;
96 que.push(tmp) ;
97 for(j = 1; j <= n ;j++)
98 {
99 mlike[tmp][j] = str[j + 1] - 'A' + 1 ;
100
101 }
102 }
103 for(i = 1; i <= n;i++)
104 {
105 scanf("%s",str);
106 int tmp = str[0] - 'A' + 1;
107 for(j = 1;j <= n;j++)
108 {
109 int a = str[j + 1] - 'a' + 1 ;
110 flike[tmp][a] = j ;
111 }
112 }
113 GaleShapley();
114
115 for(i = 1 ; i <= n;i++)
116 {
117 if(mmatch[i]!= -1)
118 {
119 printf("%c %c\n",i + 'a' - 1,mmatch[i] + 'A' -1) ;
120 }
121 }
122 printf("\n") ;
123
124
125
126
127 }
128
129 }