POJ 3487 The Stable Marriage Problem
题目大意
◇题目传送门◆
有NNN个男人向NNN个女人求婚。每个男人会从他最喜欢的女人开始一个一个地求婚。每个女人对男人也有不同的喜欢程度，当有某个女人有更喜欢的求婚者来求婚时，她会拒绝掉之前来求婚的男人。求最终哪些男人和女人会结成一对。
分析
这是一个稳定匹配的模板题
考虑这样一个算法：
我们进行第一轮的求婚：每个男人会选取名单上的第一个女人，并向她们求婚。
这时会出现两种情况：
- 一位女士还没有收到任何求婚信息，那么她一定会接受当前的男人；
- 一位女士收到了其他人的求婚信息，那么她会从这些人中选出最喜欢的人，接受他并拒绝剩下的人。
不难发现第一轮下来一定会有男人求婚没有成功。于是我们再做一轮。
我们发现这轮里参加的男人会从名单上没有拒绝他的人选出一个他最喜欢的求婚，那么也会发生如上所说的两种情况。
对于第二轮没有成功的人，我们让他们再来一次。这样重复多轮以后，所有人一定能够配对。
这个算法的正确性？
但这样看来，这个算法似乎就像个无底洞，只要有一个男人没有成功那么就会死循环。
随着轮数的增加，我们可以发现每个男人只要按照名单上的顺序挨个求婚，那么他一定会找到一个愿意接受他的女人。假若有一个男人到最后都没有成功，那么他一定是向所有的女人都求过婚的。但一个女生只要接受了求婚，那么她就一直会有男朋友。又由于左右两部分点数相同，根据 Hall 定理，一定存在一个完美匹配。这样就与有一个人没有女朋友相矛盾，故每个男人都能够找到一个女人。
并且随着轮数的增加，男人所能够找到的女人是越来越差的，而女人所接受的男人一定是越来越好的。
综上所述，我们就可以用一个队列来维护求婚失败或者没有求婚的男人，每次取出一个节点更新答案即可。
这样我们就得到了用以求解稳定匹配问题的算法——Gale-Shapley算法。
参考代码
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 100;int N;
map<char, int> mp;queue<int> q;
int pref[Maxn + 5][Maxn + 5];
int order[Maxn + 5][Maxn + 5];
int ptr[Maxn + 5];int matchx[Maxn + 5], matchy[Maxn + 5];inline void clear() {
while(!q.empty()) q.pop();memset(matchx, 0, sizeof matchx);memset(matchy, 0, sizeof matchy);memset(pref, 0, sizeof pref);memset(order, 0, sizeof order);memset(ptr, 0, sizeof ptr);mp.clear();
}void GaleShapley() {
while(!q.empty()) {
int x = q.front();q.pop();int y = pref[x][ptr[x]++];if(!matchx[y] || order[y][x] < order[y][matchx[y]]) {
int t = matchx[y];if(y) matchy[t] = 0, q.push(t);matchx[y] = x, matchy[x] = y;} else q.push(x);}for(char ch = 'a'; ch < 'z'; ch++)if(mp[ch]) printf("%c %c\n", ch, matchy[mp[ch]] + 'A' - 1);
}int main() {
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint _;scanf("%d", &_);while(_--) {
clear();scanf("%d", &N);for(int i = 1; i <= N; i++) {
char ch[100];scanf("%s", ch);mp[ch[0]] = i;}for(int i = 1; i <= N; i++) {
char ch[100];scanf("%s", ch);mp[ch[0]] = i;}for(int i = 1; i <= N; i++) {
char inp[100];scanf("%s", inp);for(int j = 2; inp[j] != '\0'; j++)pref[mp[inp[0]]][j - 1] = mp[inp[j]];ptr[mp[inp[0]]] = 1;q.push(mp[inp[0]]);}for(int i = 1; i <= N; i++) {
char inp[100];scanf("%s", inp);for(int j = 2; inp[j] != '\0'; j++)order[mp[inp[0]]][mp[inp[j]]] = j - 1;}GaleShapley();if(_) puts("");}return 0;
}