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.
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
题解
$Gale-Shapley$ 模板,可以去 Matrix67的博客 里学。
//It is made by Awson on 2018.1.17
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
using namespace std;
const int N = ;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
}
void write(int x) {
if (x > ) write(x/);
putchar(x%+);
} int couple, malelike[N+][N+], femalelike[N+][N+];
int malechoice[N+], femalechoice[N+];
char ch[N+];
queue<int>freemale; void work() {
read(couple);
for (int i = ; i < couple; i++) {
scanf("%s", ch);
freemale.push(ch[]-'a');
}
for (int i = ; i < couple; i++) {
scanf("%s", ch);
}
for (int i = ; i < couple; i++) {
scanf("%s", ch);
for (int j = ; j < +couple; j++)
malelike[i][j-] = ch[j]-'A';
}
for (int i = ; i < couple; i++) {
scanf("%s", ch);
for (int j = ; j < +couple; j++)
femalelike[i][ch[j]-'a'] = couple-(j-);
femalelike[i][couple] = -;
}
for (int i = ; i < couple; i++) {
malechoice[i] = , femalechoice[i] = couple;
}
while (!freemale.empty()) {
int male = freemale.front(), female = malelike[male][malechoice[male]];
if (femalelike[female][male] > femalelike[female][femalechoice[female]]) {
freemale.pop();
if (femalechoice[female] != couple) {
malechoice[femalechoice[female]]++; freemale.push(femalechoice[female]);
}
femalechoice[female] = male;
}else malechoice[male]++;
}
for (int i = ; i < couple; i++) printf("%c %c\n", i+'a', malelike[i][malechoice[i]]+'A');
}
int main() {
int t; read(t);
while (t--) {work(); if (t) putchar('\n'); }
return ;
}
[POJ 3487]The Stable Marriage Problem的更多相关文章
-
POJ 3487 The Stable Marriage Problem(稳定婚姻问题 模版题)
Description The stable marriage problem consists of matching members of two different sets according ...
-
poj 3478 The Stable Marriage Problem 稳定婚姻问题
题目给出n个男的和n个女的各自喜欢对方的程度,让你输出一个最佳搭配,使得他们全部人的婚姻都是稳定的. 所谓不稳婚姻是说.比方说有两对夫妇M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的 ...
-
【转】稳定婚姻问题(Stable Marriage Problem)
转自http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html 稳定婚姻是组合数学里面的一个问题. 问题大概是这样:有一个社团里 ...
-
【POJ 3487】 The Stable Marriage Problem (稳定婚姻问题)
The Stable Marriage Problem Description The stable marriage problem consists of matching members o ...
-
The Stable Marriage Problem
经典稳定婚姻问题 “稳定婚姻问题(The Stable Marriage Problem)”大致说的就是100个GG和100个MM按照自己的喜欢程度给所有异性打分排序.每个帅哥都凭自己好恶给每个MM打 ...
-
HDOJ 1914 The Stable Marriage Problem
rt 稳定婚姻匹配问题 The Stable Marriage Problem Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 6553 ...
-
【HDU1914 The Stable Marriage Problem】稳定婚姻问题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1914 题目大意:问题大概是这样:有一个社团里有n个女生和n个男生,每位女生按照她的偏爱程度将男生排序, ...
-
【HDOJ】1914 The Stable Marriage Problem
稳定婚姻问题,Gale-Shapley算法可解. /* 1914 */ #include <iostream> #include <sstream> #include < ...
-
尺取法 POJ 3320 Jessica&#39;s Reading Problem
题目传送门 /* 尺取法:先求出不同知识点的总个数tot,然后以获得知识点的个数作为界限, 更新最小值 */ #include <cstdio> #include <cmath> ...
随机推荐
-
android之Volley实现瀑布流
1.首先我们来看下主布局文件activity_main.xml. <RelativeLayout xmlns:android="http://schemas.android.com/a ...
-
一:Go编程语言规范--块、声明、作用域
1.块 块为一对大括号括住的声明和语句.块 = "{" { 语句 ";" } "}" . 除显式源码块外,还有隐式块: 全域块 包含所有的G ...
-
C#指针操作Marshal实例
static void Main(string[] args) { ,,,}; ,,,}; IntPtr pt = Marshal.AllocHGlobal(a.Length); //从source数 ...
-
some windowsphone templates
http://inspirationfeed.com/freebies/20-free-windows-phone-7-mockup-and-wireframing-resources/
-
链路层 - SLIP,PPP,
最常使用的封装格式是RFC 894定义的格式.图2 - 1显示了两种不同形式的封装格式.图中每个方框下面的数字是它们的字节长度. 两种帧格式都采用48 bit(6字节)的目的地址和源地址( 8 0 2 ...
-
微信小游戏开发之JS面向对象
//游戏开发之面向对象 //在js的开发模式中有两种模式:函数式+面向对象 //1.es5 // 拓展一:函数的申明和表达式之间的区别 // 函数的申明: // function funA(){ // ...
-
nagios监控mysql
在nagios上部署check_mysql_health 监控mysql 博客分类: 架构 本监控为基于nagios服务器主动监控方法,利用check_mysql_health实现多种监控模式: ...
-
@media 照成的问题
多出很大的空白, 原因: left 进行了叠加. 解决办法: 即,不在media里写,将其写在box下
-
ACM-素数专题(持续更新)
埃拉托斯特尼筛法,或者叫埃氏筛法(听上去似乎很高大上的样子) #include<bits/stdc++.h> using namespace std; typedef long long ...
-
PLSQL Develope连接oracle数据库配置
首先我们在讲PLSQL Develope连接oracle数据库配置之前,先讲下如果不用PLSQL Develope连接oracle数据库,那该怎么办,那就是在本机安装oracle数据库,不过这个对于配 ...