LA 3989 - Ladies' Choice 稳定婚姻问题

题目大意：

在盛大的校园舞会上有n位男生和n位女生，每人都对每个异性有一个排序，代表对他们的喜欢程度。你的任务是将男生和女生一一配对，使得男生U和女生V不存在一下情况1.男生u和女生v不是舞伴2,他们喜欢对方的程度都大于各自当前舞伴的程度。如果出现了2中的情况，他们可能擅自抛下自己的舞伴，另外组成一对。

你的任务是对于每个女生，在所有可能和她跳舞的男生中，找出她最喜欢的那一个。

思路：

看图。。。。

刘汝佳书上的原题。。划线的部分我只是想表明这个算法的。。。。丧失。。。。

稳定婚姻问题，求婚拒绝算法的实现。。。我觉得我也丧心病狂了。。。。。。情人节就是要做这种。。。。。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=1000+10; int future_wife[MAXN],future_husband[MAXN]; int order_man[MAXN][MAXN],order_woman[MAXN][MAXN],next_persue[MAXN]; queue
     
       q; //为订婚男士排队中。。。 void engage(int man,int woman) //订婚 { int getout=future_husband[woman]; //这个可怜的男人被抛弃了。当然可能为0，就是没有这个人 if(getout!=0) { q.push(getout); //兄弟，你得重新找别人了。。 future_wife[getout]=0; //抛弃现任未婚夫 } future_husband[woman]=man; future_wife[man]=woman; } int main() { int T; scanf(%d,&T); while(T--) { while(!q.empty()) q.pop(); int n; scanf(%d,&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf(%d,&order_man[i][j]); //编号为i的男士第j个喜欢的人。 future_wife[i]=0; //接下来应该向排名为1的女士求婚。 next_persue[i]=1; //没有未婚妻。 q.push(i); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int temp; scanf(%d,&temp); order_woman[i][temp]=j; //在编号为i的女士心目中，编号为temp的男士排名 } future_husband[i]=0; //没有未婚夫 } while(!q.empty()) { int man=q.front(); //该这个男的求婚了！ q.pop(); int woman=order_man[man][next_persue[man]++]; //下一个求婚对象 if(future_husband[woman]==0) //如果女士没有对象，直接订婚 engage(man,woman); else if(order_woman[woman][man]