【完备婚姻问题】
背景：现在有ｎ为大龄未婚男和ｎ位大龄未婚女，他们为了应父母之命，完成结婚生子的神圣使命

，义然决定进行相亲。每一位男生（女生）都和其余的每一位女生（男生）碰过了面，并且根据彼

此的谈话对对方产生了一定的好感，但是每个男生（女生）对每一个女生（男生）的喜好成度是不

同的，所以他们回去后都对这ｎ个女生（男生）按喜好程度进行了排名。每个男生（女生）都希望

能够得到他喜好度最高的作为自己的另一半，但是可能一个女生即很漂亮有很文雅，很多男生都为

他留了第一盏灯，所以并不是所有的男生都能追到他最喜欢的女生的；与此同时，也可能存在像Mr.

一首歌那么帅的男生的（虽然这种概率非常小，因为想Mr.一首歌那么帅的人在地球上实在是很难找

到第２个了），结果导致好多ｍｍ都想追这个帅哥，但是帅哥也只能找一个女朋友。所有的人都怕

自己的另一半出现婚后出轨的行为，即：如果这ｎ对男女结婚后，出现其中两对（设为ａ和ｂ），

ａ中的女生发现自己对ｂ中的男生的好感度大于对自己老公的好感度并且ｂ中的男生对ａ中的女生

的好感度大于对自己现在老婆的好感度，ａ中的女生就会和ｂ中的男生发生出轨行为，这是我们所

不希望看到的。
　 为了让自己的婚姻幸福美满，每个人都把自己对对方ｎ个女生（男生）的好感度的排名交给了

Mr.一首歌（现代月老），希望他能在保证组成ｎ个不出轨的家庭的前提下让每个人都找到他（她）

好感度最高的女生（男生）。
分析：根据上述背景，我们可以发现出现出轨行为发生当且仅点当“存在某两对夫妻ａ，ｂ使得ａ

中的女生发现自己对ｂ中的男生的好感度大于对自己老公的好感度并且ｂ中的男生对ａ中的女生的

好感度大于对自己现在老婆的好感度”，那么当
１）对于每一个女生，对于其现有老公她更喜欢的所有男生对她的好感度都小于他们对自己现有老

婆的好感度；
２）对于每一个男生，对于其现有老婆他更喜欢的所有女生对他的好感度都小于他们对自己现有老

公的好感度
两种情况同时满足时就不会有出轨行为发生。
算法：Gale-Shapley 算法。
实现时有两种方法：①男生表白，女生无情版②女生表白，男生无情版（稍后你会发现其实就是把

男女生的位子发生颠倒，情况不同，但是实质是一样的），下面主要来介绍①方法：
在这种情况下，每一个目前单身的男生像缺爱的野兽一样对ｎ个女生按好感度从高到低的顺序对于

某一个女生进行炮轰式的求爱，如果被求爱的女生目前单身，那么他会欣然接受，结果是两个人都

告别了单身模式；如果被求爱的女生现在已有了男朋友（因为缺爱的野兽是不会管你有没有男朋友

的），那么应为这种情况是女生无情版，所以女生为了自己的利益，会斟酌一下自己对求爱的男生

和自己现有男友的好感度的高低，如果女生对现有男友好感度更高，那么她必然拒绝求爱的男生；

如果女生对现有男友的好感度低于求爱的男生，那么她会甩掉现有的男友跟这个求爱的男生拍拖，

被甩掉的男生重新恢复单身状态，最后所有的男生都会找到女友。
对于该理论的证明：Mr.一首歌认为，虽然在模拟这种算法的过程中对于追到了女生又被抛弃的男生

很残忍（尤其可能存在某一个男生一次一次的追到女友后来又一次一次的被甩掉了），但是这样保

证了不会有男生在婚后和对比他现有妻子好感度高的女生结婚，因为在算法实现的过程中已经保证

了所有他更喜欢的女生都被更好的男生追到了，即对于那些女生，如果这个男生足够好，那么那些

女生肯定会把自己现在的男友甩掉而选择他，因为这种情况是建立在女生无情的情况下的，所以女

生为了自己的目的一定是在被求爱的过程中选最好的，又岂能把这个人放掉呢－>结论：这个男生找

不到出轨的对象。同理，对于每一个女生，她如果想出轨，势必会找一个更好的男的，但是记住我

们这里是“女生无情”的，如果又更好的男生被更好的女生相中，那么肯定不会到她手上；如果前

面的女生都看不上他觉得更好的，那么他得到的应该就是他觉得更好的，也觉是她得到了最好的。
伪代码：
while 存在单身的男生并且没有对所有的女生求过爱
{
 对每一个还能求爱的男生在他所有能求爱的女生中按好感度从大到小进行求爱
 if 女生也单身 then 也为情侣，男生告别单身
 else
      if(女生对现有男友的好感度>求爱的男生)
 　 　then 女生拒绝，求爱男生进行下一轮求爱
      else 女生接受，现有男友返回单身，求爱男生告别单身
}
例题:  hdu1522
问题大概是这样：有一个社团里有n个女生和n个男生，每位女生按照她的偏爱程度将男生排序，同

时每位男生也按照自己的偏爱程度将女生排序。然后将这n个女生和n个男生配成完备婚姻。
代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> man_idx , woman_idx;
string man[555] ,woman[555];
int man_cnt , woman_cnt;
int first[555] , n , x , y;
//M[i][j] 表示第 i 个男生第 j 个优先的女生
//W[i][j] 表示第 i 个女生对第 j 个男生的优先级
int M[555][555] , W[555][555];
int m_match[555] , w_match[555];
int add_man(string name) {
    if(man_idx.find(name)==man_idx.end()) {
        man[man_cnt] = name;
        return man_idx[name] = man_cnt ++;                                      
    }   
    return man_idx[name];
}
int add_woman(string name) {
    if(woman_idx.find(name)==woman_idx.end()) {
        woman[woman_cnt] = name;
        return woman_idx[name] = woman_cnt ++;                                          
    }   
    return woman_idx[name];
}
int main() {
    while(~scanf("%d",&n)) {
        man_idx.clear();
        woman_idx.clear();
        man_cnt = woman_cnt = 0;
        string name;
        for(int i=0;i<n;i++) {
            cin>>name;
            x = add_man(name);
            for(int j=0;j<n;j++) {
                 cin>>name;
                 y = add_woman(name);
                 M[x][j] = y; 
            }        
        }    
        for(int i=0;i<n;i++) {
            cin>>name;
            int X[555];
            x = add_woman(name);
            for(int j=0;j<n;j++) {
                 cin>>name;
                 y = add_man(name);
                 X[j] = y;
            }        
            for(int j=0;j<n;j++)
                W[x][X[j]] = j;
        }                      
        memset(m_match,-1,sizeof(m_match));
        memset(w_match,-1,sizeof(w_match));
        memset(first,0,sizeof(first));
        bool yes = true;
        while(true) {
            bool mark = true;
            int i;
            for(i=0;i<n;i++) {
                if(m_match[i] == -1) {
                     while(first[i] < n) {
                         int j = M[i][first[i]];
                         if(w_match[j] == -1) {
                              m_match[i] = j;
                              w_match[j] = i;
                              break;              
                         }          
                         if(W[j][i] < W[j][w_match[j]]) {
                              m_match[w_match[j]] = -1;
                              first[w_match[j]] ++;
                              m_match[i] = j;
                              w_match[j] = i;
                              break;           
                         }     
                         first[i] ++;
                     }              
                     if(m_match[i] == -1) mark = false;
                     break;
                }                 
            }            
            if(i == n) break;
            if(!mark) {
                 yes = false;
                 break;          
            }
        }
        if(!yes) printf("Impossible\n");
        else {
            for(int i=0;i<n;i++) 
                cout<<man[i]<<' '<<woman[m_match[i]]<<endl;
        }
    }
    return 0;    
}