转载请注明出处,谢谢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 long
using namespace std;
int couple; //总共多少对
int malelike[N][N],femalelike[N][N]; //男士对女士的喜欢程度,按降序排列,女士对男士的喜欢程度一一对应
int malechoice[N],femalechoice[N]; //男士的选择,女士的选择
int malename[N],femalename[N]; //name的HASH
char 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;
}
分享到:
相关推荐
POJ水题集-----50道左右-----增加自信啊..
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ中级-基本算法 解题报告+AC代码
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
整理的acm知识分类 ACM-POJ 算法训练指南
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
POJ3308-Paratroopers 【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 ...
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
用Java代码实现POJ(PKU)上题2494!
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle