算法：
稳定婚姻的解决方法比较简单，通俗易懂，而且还容易实现，具体有没有固定的模板我不知道，没有去找，自己模拟的，在求解的过程中，我们先把所有的男生都加到队列里，队列里的就表示当前还单身的男生，每次从队列里拿出一个男生，然后从她最喜欢的女生开始匹配，如果当前的女生尝试追求过，那么就不用追求了，如果当前的女生没有伴侣，那么可以直接匹配上，如果有伴侣，那么就看看当前这个男生和女生之前的伴侣在那个女生中更喜欢谁，如果更喜欢当先的这个男生，那么当前男生就和这个女生匹配，女生之前匹配过的直接变成单身，被扔回队列，否则，继续找下一个女生，知道找到一个能匹配上的为止，就这样一直到队列空的时候，就已经全部匹配完成了。
正确性：
对于男生来说，每次都是从最喜欢的女生开始匹配的，遇到的第一个没人能抢走的并且稳定的就是自己最终伴侣，也就是说如果之前追求过的女生被别人抢走了，那么他将永远抢不会来，因为对于女生来说，第一次被男士按照自己的意愿选择之后，每次变更匹配对象都是在自己心目中更加喜欢的，所以一旦他放弃了某个男生，那么那个男生就没希望在和他匹配，这样男生是从最优的选的，保证男生不会出轨，女生每次都是在选择她的男生中选择最优的，这样也保证了女生最后没有怨言，这样的话，最后的到的婚姻就是稳定的，至于稳定婚姻，肯定会有稳定方案，这个我暂时证明不了.<1962年，美国数学家 David Gale 和 Lloyd Shapley是这两个人发明的方法，并且证明了稳定婚姻一定会有解>。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define N 30
using namespace std;
typedef struct
{
char a ,b;
}NODE;
NODE Ans[N];
int map[N][N] ,G_b[N][N];
int nowb[N] ,nowg[N];
char nameb[N] ,nameg[N];
int mark[N][N] ,ID[200];
bool camp(NODE a ,NODE b)
{
return a.a < b.a;
}
void Marr(int n)
{
queue<int>q;
for(int i = 1 ;i <= n ;i ++)
q.push(i);
memset(mark ,0 ,sizeof(mark));
memset(nowb ,255 ,sizeof(nowb));
memset(nowg ,255 ,sizeof(nowg));
while(!q.empty())
{
int xin ,tou = q.front();
q.pop();
for(int i = 1 ;i <= n ;i ++)
{
xin = map[tou][i];
if(mark[tou][xin]) continue;
mark[tou][xin] = 1;
if(nowg[xin] == -1)
{
nowg[xin] = tou;
nowb[tou] = xin;
break;
}
else
{
if(G_b[xin][tou] > G_b[xin][nowg[xin]])
{
q.push(nowg[xin]);
nowg[xin] = tou;
nowb[tou] = xin;
break;
}
}
}
}
return ;
}
int main ()
{
int t ,n ,i ,j;
char str[30];
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
getchar();
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
ID[str[0]] = i;
nameb[i] = str[0];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
ID[str[0]] = i;
nameg[i] = str[0];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(j = 2 ;j <= n + 1 ;j ++)
map[ID[str[0]]][j-1] = ID[str[j]];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(j = 2 ;j <= n + 1 ;j ++)
G_b[ID[str[0]]][ID[str[j]]] = n - j + 2;
}
Marr(n);
for(i = 1 ;i <= n ;i ++)
Ans[i].a = nameb[i] ,Ans[i].b = nameg[nowb[i]];
sort(Ans + 1 ,Ans + n + 1 ,camp);
for(i = 1 ;i <= n ;i ++)
printf("%c %c
" ,Ans[i].a ,Ans[i].b);
if(t) printf("
");
}
return 0;
}