POJ 3487 The Stable Marriage Problem(稳定婚姻问题 模版题)
Description
The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of:
- 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
The first line gives you the number of tests. The first line of each test case contains integer n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter, female name is an upper-case letter. Then go n lines, that describe preferable lists for males. Next n lines describe preferable lists for females.
Output
For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases.
题目大意:就是稳定婚姻问题,要求男士最优
思路:直接套用Gale-Shapley算法即可
PS:直接用数字不就好了吗非要用字符……
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
using namespace std; const int MAXN = ; int pref[MAXN][MAXN], order[MAXN][MAXN], next[MAXN];
int future_husband[MAXN], future_wife[MAXN];
queue<int> que;
map<char, int> mp; void engage(int man, int woman){
int &m = future_husband[woman];
if(m){
future_wife[m] = ;
que.push(m);
}
future_husband[woman] = man;
future_wife[man] = woman;
} int n, T; void GaleShapley(){
while(!que.empty()){
int man = que.front(); que.pop();
int woman = pref[man][next[man]++];
if(!future_husband[woman] || order[woman][man] < order[woman][future_husband[woman]])
engage(man, woman);
else que.push(man);
}
for(char c = 'a'; c <= 'z'; ++c) if(mp[c])
printf("%c %c\n", c, future_wife[mp[c]] + 'A' - );
} int main(){
char s[MAXN], c[];
scanf("%d", &T);
while(T--){
if(!que.empty()) que.pop();
mp.clear();
memset(pref,,sizeof(pref));
memset(order,,sizeof(order));
memset(future_husband,,sizeof(future_husband));
memset(future_wife,,sizeof(future_wife));
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%s", c), mp[c[]] = i;
for(int i = ; i <= n; ++i) scanf("%s", c), mp[c[]] = i;
for(int i = ; i < n; ++i){
scanf("%s", s);
for(int j = ; s[j]; ++j) pref[mp[s[]]][j-] = mp[s[j]];
next[mp[s[]]] = ;
que.push(mp[s[]]);
}
for(int i = ; i < n; ++i){
scanf("%s", s);
for(int j = ; s[j]; ++j) order[mp[s[]]][mp[s[j]]] = j-;
}
GaleShapley();
if(T) printf("\n");
}
}
16MS
最新文章
- C语言位域
- JavaScript使用DeviceOne开发实战(三)仿微信应用
- 【转】 memset()的效率以及源码分析
- 另一种遍历Map的方式: Map.Entry 和 Map.entrySet()
- ArcGIS中的北京54和西安80投影坐标系详解
- mongoose学习笔记1--基础知识2
- Contest Hunter Round #70 - 连续两大交易事件杯省选模拟赛
- hdu Train Problem I
- xml装php数组
- hdu1011(树形背包)
- .net core CLI(创建VueJS||Angular结合的项目)
- HighCharts之2D颜色阶梯饼图
- ECMAScript 6 入门 ----Generator 函数
- 001_Eclipse编写第一个Java程序
- MOTT介绍(2)window安装MQTT服务器和client
- 【Hibernate步步为营】--hql查询小介
- Ubuntu16.04+cuda8.0+cuDNNV5.1 + Tensorflow+ GT 840M安装小结
- Ubuntu16.04 Xmind安装
- JavaScript数据类型转换方法汇总
- Entity Framework ";There is already an open DataReader associated with this 的解决办法