POJ3487[稳定婚姻]
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 2974 | Accepted: 1267 |
Description
- a set M of n males;
- a set F of n females;
- for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least).
A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers f over his current partner. The stable marriage A is called male-optimal if there is no other stable marriage B, where any male matches a female he prefers more than the one assigned in A.
Given preferable lists of males and females, you must find the male-optimal stable marriage.
Input
Output
Sample Input
2
3
a b c A B C
a:BAC
b:BAC
c:ACB
A:acb
B:bac
C:cab
3
a b c A B C
a:ABC
b:ABC
c:BCA
A:bac
B:acb
C:abc
Sample Output
a A
b B
c C a B
b A
c C
Source
题目大意:
有N位女士和N位男士,每位男士或者女士都对对方有个评价。
他们会形成N对夫妻,如果A和a结婚,B和b结婚,但是A更偏爱b而非a而且b也更偏爱A而非B,那么这种婚姻是不稳定的 .
求 一个稳定的 婚姻 配对。
题目要求是男士优先,也就是男士优先表白,肯定会从最喜欢的开始表白,如果对方没有男友或者表白的男士优于当前男友,就会抛弃原来的男友,而接受表白的男士,男士也成功脱光。否则男士会被拒绝,便只能考虑下一个喜欢的女士。直到所有人都脱光,不存在拒绝情况为止。
采用 Gale-Shapley算法 :
男生不停的求婚,女生不停地拒绝.
算法保证:每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的,同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的。
是不是只有唯一的稳定婚姻呢,觉得如果没有对两个人的评价完全相同的情况下,应该是唯一的.
- Source Code
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=30;
int malelike[N][N],femalelike[N][N];
int malechoice[N],femalechoice[N];
int malename[N],femalename[N];
int T,couple;char str[N];
queue<int>freemale;
int main(){
scanf("%d",&T);
while(T--){
while(!freemale.empty()) freemale.pop();
scanf("%d",&couple);
for(int i=0;i<couple;i++) scanf("%s",str),freemale.push(malename[i]=str[0]-'a');
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';
}
}
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,(couple+2)<<2);
for(int i=0;i<couple;i++) femalechoice[i]=couple;
while(!freemale.empty()){
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) putchar('\n');
}
return 0;
}
最新文章
- DBCP连接池使用问题
- lua中string.find()函数作用于汉字字符串
- POJ 3020 Antenna Placement 匈牙利算法,最大流解法 难度:1
- http://blog.csdn.net/luxiaoyu_sdc/article/details/7333024
- 【 随笔 】 D3 难吗?
- flash&;nbsp;wmode=&;quot;window&;amp;qu…
- sql sever分组查询和连接查询
- C# 《编写高质量代码改善建议》整理&;笔记 --(三)泛型&;委托&;事件
- dos命令的使用
- 阿里云web环境安装
- 手机配置代理报错invalid host header
- day11 内置函数
- CC254x/CC2540/CC2541库函数速查(转)
- oo作业总结报告2
- python实现切换代理ip
- SignalR 2 入门
- springmvc json 406
- Maven Web应用
- 【Golang 接口自动化04】 解析接口返回JSON串
- 解决Swap file &;quot;.ceshi.c.swp&;quot; already exists!问题
热门文章
- There is insufficient memory for the Java Runtime Environment to continue问题解决
- Tornado框架的初步使用
- Fedora20上Xen的安装与部署
- python——PEP8 Python 编码规范整理
- 工作流学习——Activiti流程变量五步曲
- Cocos2d-x3.2 LayerMultiplex使用说明
- iOS开发-重写description方法,自定义控制台(log)信息
- 使用NPOI读取Excel出错
- 【精】iOS GCD 具体解释
- 自己动手制作更好用的markdown编辑器-02