稳定婚姻问题（自己的总结）

     稳定婚姻问题就是给你n个男的，n个女的，然后给你每个男生中女生的排名，和女生心目中男生的排名，然后让你匹配成n对，使婚姻稳定，假如a和b匹配,c和d匹配，如果a认为d比b好，同时d也认为a比c好，那么ad就有可能私奔，这样就导致了婚姻的不稳定，稳定婚姻就是找到一种解决方案让婚姻稳定

算法：

      稳定婚姻的解决方法比较简单，通俗易懂，而且还容易实现，具体有没有固定的模板我不知道，没有去找，自己模拟的，在求解的过程中，我们先把所有的男生都加到队列里，队列里的就表示当前还单身的男生，每次从队列里拿出一个男生，然后从她最喜欢的女生开始匹配，如果当前的女生尝试追求过，那么就不用追求了，如果当前的女生没有伴侣，那么可以直接匹配上，如果有伴侣，那么就看看当前这个男生和女生之前的伴侣在那个女生中更喜欢谁，如果更喜欢当先的这个男生，那么当前男生就和这个女生匹配，女生之前匹配过的直接变成单身，被扔回队列，否则，继续找下一个女生，知道找到一个能匹配上的为止，就这样一直到队列空的时候，就已经全部匹配完成了。

正确性：
        对于男生来说，每次都是从最喜欢的女生开始匹配的，遇到的第一个没人能抢走的并且稳定的就是自己最终伴侣，也就是说如果之前追求过的女生被别人抢走了，那么他将永远抢不会来，因为对于女生来说，第一次被男士按照自己的意愿选择之后，每次变更匹配对象都是在自己心目中更加喜欢的，所以一旦他放弃了某个男生，那么那个男生就没希望在和他匹配，这样男生是从最优的选的，保证男生不会出轨，女生每次都是在选择她的男生中选择最优的，这样也保证了女生最后没有怨言，这样的话，最后的到的婚姻就是稳定的，至于稳定婚姻，肯定会有稳定方案，这个我暂时证明不了，是看别人说的。

自己所以写的一个模板，有点难看！！！！

#include<stdio.h>
#include<string.h>
#include<queue>

#define N 30

using namespace std;

int G_b[N][N];//男孩在女孩心中的分数 
int nowB[N] ,nowG[N]; //当前匹配结果 
char Name_B[N] ,Name_G[N]; //记录名字 
int map[N][N];//男孩喜欢的女孩的顺序 
int mark[N][N];//是否尝试求婚过 
int hash[200];//mark名字用的 

void Marr(int n)
{
   queue<int>q;
   for(int i = 1 ;i <= n ;i ++)
   q.push(i);
   memset(nowB ,255 ,sizeof(nowB));
   memset(nowG ,255 ,sizeof(nowG));
   memset(mark ,0 ,sizeof(mark));
   while(!q.empty())
   {
      int tou = q.front();
      q.pop();  
      for(int ii = 1 ;ii <= n ;ii ++)
      {
         int i = map[tou][ii];  
         if(mark[tou][i]) continue;
         mark[tou][i] = 1;
         if(nowG[i] == -1) 
         {    
            nowG[i] = tou;
            nowB[tou] = i;
            break;
         }
         else
         {
            if(G_b[i][tou] > G_b[i][nowG[i]])
            {  
                q.push(nowG[i]);
                nowG[i] = tou;
                nowB[tou] = i;
                break;
            }
         }
      }
   }
}


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);
         hash[str[0]] = i;
         Name_B[i] = str[0];
      }
      for(i = 1 ;i <= n ;i ++)
      {
         scanf("%s" ,str);
         hash[str[0]] = i;
         Name_G[i] = str[0]; 
      } 
      for(i = 1 ;i <= n ;i ++)
      {
         scanf("%s" ,str);
         for(j = 2 ;j <= n + 1 ;j ++)
         map[hash[str[0]]][j-1] = hash[str[j]];
      }
      for(i = 1 ;i <= n ;i ++)
      {
         scanf("%s" ,str);
         for(j = 2 ;j <= n + 1 ;j ++)
         G_b[hash[str[0]]][hash[str[j]]] = n - j + 2;            
      }
      Marr(n);
      for(i = 1 ;i <= n ;i ++)
      printf("%c %c " ,Name_B[i] ,Name_G[nowB[i]]);
      if(t) puts("");
   }
   return 0;
}