また図論-安定結婚アルゴリズムのC++実現

安定した婚姻は1つのとても面白い二分図の問題で、これは生活の中で1つの典型的な問題で、通俗的に述べることができます:現在N人の男子学生とN人の女子学生が最後に安定した婚姻の家庭を構成して、過程が始まる前に男子学生と女子学生はそれぞれの心の中ですべて好きな程度によってN人の異性に対してそれぞれの順位があります.そして、自分のオブジェクトを選択し始めました.目的は、すべての人が最適なオブジェクトを見つけることです.次は私のC++コード実装です.
 

#include
#include
#include
#include
using namespace std;
struct woman{
 bool free;
 vectorv;
 int h   ;
};
struct best_woman
{
  int num;                //  
  int Rank;              //  
  best_woman(int n,int i):num(n),Rank(i){}
 friend bool operator w2.Rank;
 }
};
struct man{
 bool free ;
 priority_queuev;
};
class marry
{
private:
 int n;
 vectorM;
 vectorWM;
public:
 marry(int n):n(n)
 {
  man mtmp;
  woman wmtmp;
  for(int i=0;i<=n;i++)     //n   ， 1  ，    
  {
   M.push_back(mtmp);
   WM.push_back(wmtmp);
   M[i].free=1;
   WM[i].free=1;
   WM[i].v.push_back(0);
  }
 }
 void man_priority(int j,int i,int Rank)  // j     i      
 {
    best_woman wtmp(i,Rank);
    M[j].v.push(wtmp);
 }
void woman_priority(int j,int Rank)
 {

    WM[j].v.push_back(Rank);
 }
 void m_marry()
 {
  queueQ;
  for(int i=1;i<=n;i++)
   Q.push(i);
  while(!Q.empty())
  {
    int m=Q.front();Q.pop();
    best_woman bw=M[m].v.top();M[m].v.pop();
    int w=bw.num;
    if(WM[w].free)
   {
    WM[w].free=0;
    WM[w].h=m;
   }
   else if(WM[w].v[WM[w].h]>WM[w].v[m])
    {
      Q.push(WM[w].h);
      WM[w].h=m;
      }
   else
      Q.push(m);
   }
 }
 void print()
 {
       for(int i=1;i<=n;i++)
     cout<>n)
   {
     marry M(n);
    int tmp;
  for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
   {
    cin>>tmp;
    M.man_priority(i,j,tmp);
   }
   for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
   {
    cin>>tmp;
    M.woman_priority(i,tmp);
   }
       M.m_marry();
    M.print();
    cout<

 
次はin.txtのテストデータ:
3
2 1 3
3 1 2
3 2 1
3 1 2
2 3 1
3 1 2
2
1 2
2 1
2 1
1 2
4
1 2 3 4
1 4 3 2
2 1 3 4
4 2 3 1
3 4 2 1
3 1 4 2
2 4 3 1
3 2 1 4
 
そしてtxtの結果は、次のとおりです.
woman 1,man 1
woman 2,man 3
woman 3,man 2
 
woman 1,man 1
woman 2,man 2
 
woman 1,man 3
woman 2,man 4
woman 3,man 1
woman 4,man 2
プログラムに問題はありません.このアルゴリズムの核心は、男性がまず自分の優先リストに従って女性を選ぶことです.そして、女性が自分のリストと告白された男性からこの男性を受け入れるかどうかを見ることです.私は優先キューというデータ構造を使っているので、アルゴリズム全体の効率はO(n^2 logn)です.もちろん、空間効率はO(n^2)であり,ここでは最適化の可能性はないようだが,このアルゴリズムは性別差別があることも容易に見られるが,これはこのアルゴリズム自体の欠陥であり,改善の可能性もない.