解决特定情况下的匹配问题的C ++程序

这是一个C ++程序，用于解决给定特定情况下的匹配问题。在这里，给出了N个男人和N个女人，每个人都按照优先顺序对异性的所有成员进行了排名，将男人和女人结婚，这样就不会有两个异性会宁愿彼此相爱的人目前的合作伙伴。如果没有这样的人，那么所有的婚姻都是“稳定的”。

演算法

Begin
   function WomenPrefersMenOverMen1():
   A) Check if women prefer men over her current engagement men1
   B) If men1 comes before men in list of women, then women prefer her current engagement.
   C) If men comes before men1 in womens's list, then free her current engagement and engage her with men.
End
Begin
   function stablewedding():
   1) Boys are numbered as 0 to N-1.
   2) Girls are numbered as N to 2N-1.
   3) While men are free
      A) Pick the first free man
      B) 根据自由男人的喜好，一对一地送给所有女人。
      C) 偏爱的女人是自由的，男人和女人成为伴侣。
      D) If woman is not free 查找当前女性订婚
      E)如果女人比他目前的订婚男人更喜欢男人1，然后打破女人和男人的交往，让男人和女人交往。
End

示例

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 4
bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) {
   for (int i = 0; i < N; i++) {
      if (prefer[w][i] == m1)
         return true;
      if (prefer[w][i] == m)
         return false;
   }
}
void stablewedding(int prefer[2*N][N]) {
   int wPartner[N]; //Initialize an array to store partner of women.
   bool mFree[N]; //Initialize an array to store availability of men.
   //免费初始化所有男人和女人。
   memset(wPartner, -1, sizeof(wPartner));
   memset(mFree, false, sizeof(mFree));
   int freeCnt = N;
   while (freeCnt > 0) { //While men is free
      int m; //Pick the first free man
      //根据自由男人的喜好，一对一地送给所有女人。
      for (m = 0; m < N; m++)
         if (mFree[m] == false)
            break;
      for (int i = 0; i < N && mFree[m] == false; i++) {
         int w = prefer[m][i];
         //偏爱的女人是自由的，男人和女人成为伴侣。
         if (wPartner[w-N] == -1) {
            wPartner[w-N] = m;
            mFree[m] = true;
            freeCnt--;
         } else { //If w is not free
             //查找当前女性订婚
            int m1 = wPartner[w-N];
            //如果女人比他目前的订婚男人更喜欢男人1， 
            //然后打破女人和男人的交往，让男人和女人交往。
            if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) {
               wPartner[w-N] = m;
               mFree[m] = true;
               mFree[m1] = false;
            }
         }      
      }
   }
   cout << "Woman Man" << endl;
   for (int i = 0; i < N; i++)
      cout << " " << i+N << "\t" << wPartner[i] << endl;
}
int main() {
   int p[2*N][N] = { 
      {7, 5, 6, 4},
      {5, 4, 7, 6},
      {4, 5, 7, 6},
      {4, 5, 7, 6},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
   };
   stablewedding(p);
   return 0;
}

输出结果

Woman Man
4 3
5 1
6 2
7 0