[POJ 3487]The Stable Marriage Problem

时间:2022-07-26 09:48:12

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的更多相关文章

  1. POJ 3487 The Stable Marriage Problem(稳定婚姻问题 模版题)

    Description The stable marriage problem consists of matching members of two different sets according ...

  2. poj 3478 The Stable Marriage Problem 稳定婚姻问题

    题目给出n个男的和n个女的各自喜欢对方的程度,让你输出一个最佳搭配,使得他们全部人的婚姻都是稳定的. 所谓不稳婚姻是说.比方说有两对夫妇M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的 ...

  3. 【转】稳定婚姻问题&lpar;Stable Marriage Problem&rpar;

    转自http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html 稳定婚姻是组合数学里面的一个问题. 问题大概是这样:有一个社团里 ...

  4. 【POJ 3487】 The Stable Marriage Problem &lpar;稳定婚姻问题&rpar;

    The Stable Marriage Problem   Description The stable marriage problem consists of matching members o ...

  5. The Stable Marriage Problem

    经典稳定婚姻问题 “稳定婚姻问题(The Stable Marriage Problem)”大致说的就是100个GG和100个MM按照自己的喜欢程度给所有异性打分排序.每个帅哥都凭自己好恶给每个MM打 ...

  6. HDOJ 1914 The Stable Marriage Problem

    rt 稳定婚姻匹配问题 The Stable Marriage Problem Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 6553 ...

  7. 【HDU1914 The Stable Marriage Problem】稳定婚姻问题

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1914 题目大意:问题大概是这样:有一个社团里有n个女生和n个男生,每位女生按照她的偏爱程度将男生排序, ...

  8. 【HDOJ】1914 The Stable Marriage Problem

    稳定婚姻问题,Gale-Shapley算法可解. /* 1914 */ #include <iostream> #include <sstream> #include < ...

  9. 尺取法 POJ 3320 Jessica&&num;39&semi;s Reading Problem

    题目传送门 /* 尺取法:先求出不同知识点的总个数tot,然后以获得知识点的个数作为界限, 更新最小值 */ #include <cstdio> #include <cmath&gt ...

随机推荐

  1. android之Volley实现瀑布流

    1.首先我们来看下主布局文件activity_main.xml. <RelativeLayout xmlns:android="http://schemas.android.com/a ...

  2. 一:Go编程语言规范--块、声明、作用域

    1.块 块为一对大括号括住的声明和语句.块 = "{" { 语句 ";" } "}" . 除显式源码块外,还有隐式块: 全域块 包含所有的G ...

  3. C&num;指针操作Marshal实例

    static void Main(string[] args) { ,,,}; ,,,}; IntPtr pt = Marshal.AllocHGlobal(a.Length); //从source数 ...

  4. some windowsphone templates

    http://inspirationfeed.com/freebies/20-free-windows-phone-7-mockup-and-wireframing-resources/

  5. 链路层 - SLIP,PPP,

    最常使用的封装格式是RFC 894定义的格式.图2 - 1显示了两种不同形式的封装格式.图中每个方框下面的数字是它们的字节长度. 两种帧格式都采用48 bit(6字节)的目的地址和源地址( 8 0 2 ...

  6. 微信小游戏开发之JS面向对象

    //游戏开发之面向对象 //在js的开发模式中有两种模式:函数式+面向对象 //1.es5 // 拓展一:函数的申明和表达式之间的区别 // 函数的申明: // function funA(){ // ...

  7. nagios监控mysql

    在nagios上部署check_mysql_health 监控mysql 博客分类: 架构   本监控为基于nagios服务器主动监控方法,利用check_mysql_health实现多种监控模式:  ...

  8. &commat;media 照成的问题

    多出很大的空白, 原因: left 进行了叠加. 解决办法: 即,不在media里写,将其写在box下

  9. ACM-素数专题(持续更新)

    埃拉托斯特尼筛法,或者叫埃氏筛法(听上去似乎很高大上的样子) #include<bits/stdc++.h> using namespace std; typedef long long ...

  10. PLSQL Develope连接oracle数据库配置

    首先我们在讲PLSQL Develope连接oracle数据库配置之前,先讲下如果不用PLSQL Develope连接oracle数据库,那该怎么办,那就是在本机安装oracle数据库,不过这个对于配 ...