稳定匹配算法

稳定匹配算法的经典问题即稳定婚姻问题。
“稳定婚姻问题”在生活中是一个典型的问题,通俗地可叙述为:当前有N位男生和N位女生最后要组成稳定的婚姻家庭,过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序.然后开始选择自己的对象,其规则是:男生第一天均向各自最喜欢的女生写一封“情书”。

策略

我们采用男人优先的策略。首先各个男人按照自己的喜好由高到低向女人发送情书。如果收到情书的女人还没有男朋友，则和这个男人组成男女关系。如果这个女人已经有男朋友了，则比较现男友和发情书的男人的喜好程度，若现男友喜好度低，则果断分手追求新男人，否则拒绝。
这种策略必然有最优解，证明略

代码实现

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 1024;
stack<int> s; //存储没有找到女朋友的男生
int n;
int man[maxn][maxn],woman[maxn][maxn],pos[maxn],cur[maxn];
/*
man: 男生的喜好表
woman: 女生的喜好表
pos: 记录每个男生当前选择的女生
cur: 记录当前女生的男朋友，若没有则赋初值-1
*/
void init()
{
  memset(cur,-1,sizeof(cur));
  memset(pos,0,sizeof(pos));
  for(int i=0;i<n;i++)  s.push(n);
}

void stable_marriage()
{
  while(!s.empty())
  {
    int f = s.top();s.pop(); //当前男生
    int t = man[f][pos[f]++];  //当前选择女生
    if(cur[t] == -1)  //如果当前女生没有男朋友
    {
      cur[t] = f;
      continue;
    }
    else
    {
      int pre,now; //比较喜好程度
      for(pre=0;woman[t][pre] != cur[t];pre++);
      for(now=0;woman[t][now] != f;now++);
      if(now < pre)  //如果当前男生的喜好度更高，则抛弃现男友
      {
        s.push(cur[t]);
        cur[t] = f;
      }
      else  s.push(f);  //拒绝当前男生
    }
  }
}