可能更好的阅读体验！

Stable Matching问题

假设有 $n$ 个男生，$n$个女生$~(n \le 10^3)$，每个人都在自己心中对 $n$ 个异性有一定的心仪程度排序。

我们定义一个Unstable matching为：如果存在一对不是情侣的男女符合以下情况：

对于该男，该女在他的心仪列表中处于现任女友的前面，对于该女，该男在他的心仪列表中亦处于现任男友的前面，那么这对男女必然有私奔的倾向、、

这样的情景即为Unstable matching。反之，若不存在这样一对有私奔倾向的男女，即为Stable matching。

现在，我们的任务就是构造一种Stable Matching。

Gale-Shapley算法：

（没错 Gale-Shapley 是两个老哥的名字）

1、$n$个男生去匹配他们的最心仪女生；

2、所有女生挑选喜欢他中的最心仪的男生；

3、被拒绝的男生把女生从心仪列表里面删掉（伤心了）；

4、之后男生再选择最心仪的女生，女生依然选择向他表白的最心仪的男生（可以淘汰原来的）；

PS：这里有一个很重要的特点：一旦一位女性找到配偶，她将不会再单身，只会替换成更好的（下文会提到）。

伪代码：

首先初始化所有男生的状态为自由

while 当男生没有未曾被匹配过，并且也没有向所有女生表白过{

每个男生按照对女生的喜欢程度选择舞伴

if 女生未被匹配到，则与男生进行配对

if 女生与已匹配的男生相比更喜欢当前的这个男生，则拆散重新匹配
else 该女生拒绝成为男生的舞伴

}

一、正确性证明：

---

先来考虑一下存不存在匹配：

假设：存在男性 Z 在算法终止后仍然未匹配到女性（孤独终老）

由此可知，一定有一位女性，假设为 A，也没有匹配到男性（抵制一夫多妻制）

根据算法，一位单身女性一定会同意向她求婚的男性，且女性一旦有配偶就不会再次单身，所以女性 A 一定没有被求过婚

根据算法 while 循环条件，男性 Z 一定向所有女性求过婚算法才会终止

因此男性 Z 向女性 A 求过婚

产生矛盾，假设不成立，证明完毕

考虑 $B_i$ 匹配到 $G_i$，$B_j$ 匹配到 $G_j$ 并且是一个不稳定匹配。

那么就有 $B_i$ 更喜欢 $G_j$，$G_j$更喜欢$B_i$

那么 $B_i$ 一定会在 $G_i$ 之前先选择向 $G_j$ 表白，而 $G_j$ 也会同意（不稳定情况的定义），但是 $G_j$ 最后却是跟 $B_j$ 走了，这是违反我们的定义的（双方互相喜欢，女方却选择了一个更差的男生，不科学啊）

二、时间复杂度

---

在最差情况下，显然是 $O(n^2)$ 的。。

三、一个有趣的更强的结论

---

我们直接给出结论:

所有男生最后找到的一定是最佳的伴侣，而所有女生找到的一定是最差的伴侣。

咳咳，听起来感觉很离谱，因为男生有可能因为女生找到了更好的伴侣而被抛弃（惨）

诶，但是我们理性分析一波：

对于男生 A，

设最后他的女友是在他当初的心仪列表的第i位，那么在i位之前的那些女生，他是怎么追也追不到的：

因为即使那个女生X，也必然会有比他心仪的对象——男生Y，

而男生Y既然在当时向该女生表白，表明他认为比Y更好的女生都拒绝了他，而如果Y也拒绝了他，他最后在一起的女生必定排在Y之后。

所以，X 和 Y 是注定要在一起的，男生 A 选择女生X只是造成了一个 Unstable Matching。

诶，所以嘛，男生没有追到的那些女生，都是他太逊了硬实力不够，那么换句话说，他最后追到的女生是他最好的选择了。

女生最劣分配同理也可以证明。

这是一种感性的证明方法，意会即可。

四、代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;

int n;
int Map_Man[N][N],Map_Woman[N][N];
int Man_Partner[N],Woman_Partner[N];
int Propose[N];		//男生的求婚目标（第几顺位的女生） 
queue <int> Free_Man;		//未婚男生队列（男生追女生） 

inline int read(){
    int x=0,f=1;
	char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
	n=read();
	memset(Man_Partner,-1,sizeof(Man_Partner));
	memset(Woman_Partner,-1,sizeof(Woman_Partner));
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			Map_Man[i][j]=read();	
	//第i个男生的第j顺位心仪女生是Map_Man[i][j] 
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++){
			int x=read();
			Map_Woman[i][x]=j;
		}
	//注意：第i个女生对第j个男生的心仪程度是Map_Woman[i][j] 
	
	for (int i=1;i<=n;i++)
		Free_Man.push(i);		//将所有男生加入未婚男生队列
	
	while (!Free_Man.empty()){
		int i=Free_Man.front();
		Propose[i]++;
		int like=Map_Man[i][Propose[i]];		//like为求婚目标 
		if (Woman_Partner[like]==-1){	//如果女生未婚 
			Woman_Partner[like]=i;		//互相选定
			Man_Partner[i]=like;
			Free_Man.pop();		//退出未婚队列 
		}
		else if (Map_Woman[like][i]<Map_Woman[like][Woman_Partner[like]]){		//女生找到了更好的男生 
			Man_Partner[Woman_Partner[like]]=-1;		//男生被淘汰，进入未婚状态
			Free_Man.push(Woman_Partner[like]); 
			Woman_Partner[like]=i;		//互相选定
			Man_Partner[i]=like;
			Free_Man.pop();
		}
	}
	
	for (int i=1;i<=n;i++)
		printf("%d\n",Woman_Partner[i]);
	return 0;
}

---

部分内容引用自：

1.https://www.cnblogs.com/jielongAI/p/9463029.html

2.https://blog.csdn.net/alwaysik/article/details/78949250

3.https://zhuanlan.zhihu.com/p/225925804