首页 > 代码库 > POJ3487[稳定婚姻]
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
23a b c A B Ca:BACb:BACc:ACBA:acbB:bacC:cab3a b c A B Ca:ABCb:ABCc:BCAA:bacB:acbC:abc
Sample Output
a Ab Bc Ca Bb Ac 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;}
POJ3487[稳定婚姻]