Stable Matching-稳定匹配问题【G-S算法，c++】

题目描述：(Gale-Shapley算法)

Teenagers from the local high school have asked you to help them with the organization of next year’s Prom. The idea is to find a suitable date for everyone in the class in a fair and civilized way. So, they have organized a web site where all students, boys and girls, state their preferences among the class members, by ordering all the possible candidates. Your mission is to keep everyone as happy as possible. Assume that there are equal numbers of boys and girls.
当地高中的青少年要求您帮助他们组织明年的舞会。 想法是以公平文明的方式为班上的每个人找到合适的约会对象。 因此，他们组织了一个网站，所有学生，男孩和女孩，通过订购所有可能的候选人，在班级成员中陈述他们的偏好。 你的任务是让每个人都尽可能开心。 假设男孩和女孩的数量相等。

Given a set of preferences, set up the blind dates such that there are no other two people of opposite sex who would both rather have each other than their current partners. Since it was decided that the Prom was Ladies’ Choice, we want to produce the best possible choice for the girls.
给定一组偏好，设置相亲日期，使得没有其他两个异性比他们现在的伴侣更愿意拥有对方。 由于决定舞会是女士们的选择，我们希望为女孩们提供最好的选择。
Input:
Input consists of multiple test cases the first line of the input contains the number of test cases.
There is a blank line before each dataset.
The input for each dataset consists of a positive integer N, not greater than 1,000, indicating the number of couples in theclass. Next, there are N lines, each onecontaining the all the integers from 1 to N,ordered according to the girl’s preferences. Next, there are N lines, each one containing all the integers from 1 to N, ordered according to the boy’s preferences.
输入由多个测试用例组成
输入的第一行包含测试用例的数量。
每个数据集前有一个空行。
每个数据集的输入由一个不大于 1000 的正整数 N 组成，表示该类中的夫妻数量。 接下来，有N行，每行包含从1到N的所有整数，按照女孩的喜好排序。 接下来，有 N 行，每行包含从 1 到 N 的所有整数，按照男孩的喜好排序。
Output:
The output for each dataset consists of a sequence of N lines, where the i-th line containsthe number of the boy assigned to the i-th girl (from 1 to N).
Print a blank line between datasets.
每个数据集的输出由一系列 N 行组成，其中第 i 行包含分配给第 i 个女孩的男孩的编号（从 1 到 N）。
在数据集之间打印一个空行。
Sample Input:
1
5
1 2 3 5 4
5 2 4 3 1
3 5 1 2 4
3 4 2 1 5
4 5 1 2 3
2 5 4 1 3
3 2 4 1 5
1 2 4 3 5
4 1 2 5 3
5 3 2 4 1
Sample Output:
1
2
5
3
4

解题思路一：G-S算法(Gale-Shapley算法)

基本思想：以不断”求婚”的过程来逼近一个稳定匹配的状态
伪代码：(注意男生与女生的优先级，如果是女生先选，那么下列伪代码男女互换即可)

初始所有的m∈M和w∈W都是自由的
While 存在男人m是自由的且没有对每个女人都求过婚选择这样一个男人m令w是m的优先表中m还没有求过婚的排名最高的女人If    w是自由的    then(m,w)变成约会状态Else    w当前正在与m'约会If    w相较于m更爱m'    thenm保持自由Else    w相较于m'更爱m(m,w)变成约会状态m'变成自由状态EndifEndif
Endwhile
输出已约会的集合S.

代码思想：首先创建两个二维数组记录男女的偏好，再创建两个一维数组记录男女目前的配偶（0代表自由状态）。
我们将这两个一维数组的第一个元素即：坐标为0的元素用来记录目前已匹配的人数。而将二维数组的每个一维数组坐标为0的元素记录对应男生和女生目前只能从第几号备胎开始选择。
即我们每次找到编号最小且未配偶的女生，然后从其备胎里面找下一位。若备胎未配偶那么直接配对。若备胎已配偶那么看该备胎是喜欢她还是喜欢前任。如果喜欢前任，就继续换下一个备胎。如果喜欢她就直接配对，前任自由。（总体就是这样一个思路）

c++代码：（需要注意输出格式和每次清空数组）
（大家尽量自己手敲一遍加深印象哦！）

#include<bits/stdc++.h>
using namespace std;
const int maxN=1009;
int woman[maxN]={0},man[maxN]={0};//woman[0]对应该女生只能从该号开始选
int manlist[maxN][maxN]={0},womanlist[maxN][maxN]={0};
bool lovemore(int m,int w,int n){for(int i=1;i<=n;++i)if(manlist[m][i]==w) return true;//更喜欢现在的else if(manlist[m][i]==man[m]) return false;//更喜欢之前的return false;
}
void stableMatching(int n){int m,w;while(woman[0]!=n){//woman[0]记录已经匹配的女生w=m=0;while(woman[++w]!=0);m=womanlist[w][++womanlist[w][0]];//[0]对应该女生只能从该号开始选if(man[m]){//如果该男生已经匹配了if(lovemore(m,w,n)){//更喜欢现在的woman[man[m]]=0;//之前喜欢该男生的女生自由woman[w]=m;//当前女生喜欢m号manman[m]=w;//该男生喜欢变为当前女生}else continue;//w继续找列表下一个}else{woman[w]=m;++woman[0];man[m]=w;++man[0];}}}
void getprefer(int N){for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)cin>>womanlist[i][j];for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)cin>>manlist[i][j];
}
void output(int n){for(int i=1;i<=n;++i){cout<<woman[i]<<endl;}
}
int main(){int num,N;cin>>num;while(num--){cin>>N;getprefer(N);stableMatching(N);output(N);memset(man, 0, sizeof(man));memset(woman, 0, sizeof(woman));memset(manlist, 0, sizeof(manlist));memset(womanlist, 0, sizeof(womanlist));if(num>=1) cout<<endl;}return 0;
}

时间复杂度：O(n^2)
空间复杂度：O(n^2)
有关G-S算法想了解更多的参考下面的链接。
Reference：
https://blog.rulinxing.com/Stable%20Matching-%E7%A8%B3%E5%AE%9A%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98.html