POJ 3487 The Stable Marriage Problem(Gale-Shapley算法求稳定婚姻)

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：有N位女士和N位男士，每位男士或者女士都对对方有个评价。他们会形成N对夫妻，如果A和a结婚，B和b结婚，但是A更偏爱b而非a而且b也更偏爱A而非B，那么这种婚姻是不稳定的

http://poj.org/problem?id=3487

现在要求出当前N对的稳定婚姻

这里用的是Gale-Shapley算法，传说中的表白--拒绝算法

题目要求是男士优先，也就是男士优先表白，肯定会从最喜欢的开始表白，如果对方没有男友或者表白的男士优于当前男友，就会抛弃原来的男友，而接受表白的男士，男士也成功脱光。否则男士会被拒绝，便只能考虑下一个喜欢的女士。直到所有人都脱光，不存在拒绝情况为止。

队列实现，将自由男一个个拿出来，寻找女士一个个进行匹配。

感觉上先表白的男士会沾光，其实肯定不然。。。。是不是只有唯一的稳定婚姻呢，觉得如果没有对两个人的评价完全相同的情况下，应该是唯一的

#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<cmath>#include<algorithm>#define N 30#define inf 1<<29#define MOD 2007#define LL long longusing namespace std;int couple;                  //总共多少对int malelike[N][N],femalelike[N][N];   //男士对女士的喜欢程度，按降序排列，女士对男士的喜欢程度一一对应int malechoice[N],femalechoice[N];   //男士的选择，女士的选择int malename[N],femalename[N];   //name的HASHchar str[N];queue<int>freemale;   //没有配对的男士int main(){    int t;    scanf("%d",&t);    while(t--){        scanf("%d",&couple);        //清空队列        while(!freemale.empty())            freemale.pop();        //将男士的名字存下，初始都没有配对        for(int i=0;i<couple;i++){            scanf("%s",str);            malename[i]=str[0]-'a';            freemale.push(malename[i]);        }        //将名字排序，便于字典序        sort(malename,malename+couple);        for(int i=0;i<couple;i++){            scanf("%s",str);            femalename[i]=str[0]-'A';        }        //男士对女士的印象，按降序排列        for(int i=0;i<couple;i++){            scanf("%s",str);            for(int j=0;j<couple;j++)                malelike[i][j]=str[j+2]-'A';        }        //女士对男士的打分，添加虚拟人物，编号couple,为女士的初始对象，        for(int i=0;i<couple;i++){            scanf("%s",str);            for(int j=0;j<couple;j++)                femalelike[i][str[j+2]-'a']=couple-j;            femalelike[i][couple]=0;        }        //一开始男士的期望都是最喜欢的女士        memset(malechoice,0,sizeof(malechoice));        //女士先初始一个对象        for(int i=0;i<couple;i++)            femalechoice[i]=couple;        while(!freemale.empty()){            //找出一个未配对的男士，注意不要习惯性的POP            int male=freemale.front();            //男士心仪的女士            int female=malelike[male][malechoice[male]];            //如果当前男士比原来的男友更好            if(femalelike[female][male]>femalelike[female][femalechoice[female]]){                //成功脱光                freemale.pop();                //如果有前男友，则打回光棍，并且考虑下一个对象                //不要把虚拟的人物加入队列，否则就死循环或者错误                if(femalechoice[female]!=couple){                    freemale.push(femalechoice[female]);                    malechoice[femalechoice[female]]++;                }                //当前男友为这位男士                femalechoice[female]=male;            }            else             //如果被女士拒绝，则要考虑下一个对象                malechoice[male]++;        }        for(int i=0;i<couple;i++)            printf("%c %c\n",malename[i]+'a',malelike[malename[i]][malechoice[malename[i]]]+'A');        if(t) puts("");    }    return 0;}