稳定婚姻问题（Gale-Shapley算法）

前言

今天 duck、香饽饽老板和彬彬一起出了个模拟赛，赛时T2想到了跟正解很接近的做法，但最后还是打挂了then喜提0pts，后面 duck 讲题的时候才知道是稳定婚姻板题。

看完证明之后觉得很妙，遂开坑。

只是简单整理，图一乐子吧算是。

说是稳定婚姻问题，但其实我觉得更合适的叫法是属性稳定分配问题，毕竟用简单几个维度来判断两人是否更适合结婚是很不明智的呢。QwQ

所以说恋综什么的完全就是无脑人群的流量游戏而已吧。

问题概述

有两类人群，分别为一群男孩子和一群女孩子，每个男孩子对女孩子们都有一个好感度排序，一个女孩子的排序越靠前则该男孩子越喜欢该女孩子，女孩子同理。
现在有两段恋爱关系：男孩子 \(A\) 与女孩子 \(A'\) 在一起了，男孩子 \(B\) 和女孩子 \(B'\) 在一起了。

但是当女孩子 \(B'\) 更喜欢男孩子 \(A\)、男孩子 \(A\) 也更喜欢女孩子 \(B'\) 时，则称这两段恋爱关系是不稳定的。

现在有 \(n\) 个男孩子和 \(n\) 个女孩子，问如何匹配才能使得所有的分配关系都是稳定的。

\(\text{Gale-Shapley}\) 算法

简单概述就是男孩子主动，女孩子在追求者中选最优。

匹配进行若干轮，直到所有人匹配成功时才会结束匹配。

在每一轮中，每个单身的男孩子都优先追求自己更喜欢的女孩子。

在面对一个男孩子表白时，女孩子会遇到如下局面：

• 没有男孩子表白：没对象then专心AK NOI。

• 有一个男孩子表白：和该男孩子在一起。

• 有一堆男孩子表白：选最优的那个男孩子。

注意第三种情况，这种情况下意味着有的男孩子可能会失去对象重归单身状态，此时他便需要在下一轮中重新追求一个女孩子。

重复若干轮，最后可证明每个人都一定会匹配上，并且整体的匹配关系是稳定的。

该算法流程体现的恋爱观我真的很难认可。

隔行如隔山，我祝他们成功。

证明

简单证明一下为什么该算法保证一定有稳定匹配方案。

在每一轮匹配中，每个没有对象的男孩子都会至少向所有女孩子中的一个女孩子表白，一个男孩子经历了若干次在一起和分手后，他一定不会再与和他分过手或者拒绝过他的女孩子再在一起，因为和他分过手/拒绝了他的女孩子被他表白时一定会拥有一个更优的对象，此时这个男孩子会在该轮中继续选择更劣的一位女孩子进行表白。

最后在进行了超级超级多轮之后，若一个男孩子还是没有找到匹配，此时他一定跟所有的女孩子都表白过了，而每个女孩子在被表白过之后一定不会再变为单身状态，所以此时所有女孩子都一定有相应的匹配对象了。

于是为什么一定有匹配方案的问题就解决了。

接下来证明为什么此时的方案一定是稳定分配。

理解了算法流程之后我们不难发现，男孩子的对象只会越变越差，女孩子的对象只会越来越优。

假设当前男孩子 \(A\) 和女孩子 \(B'\) 都有了各自的对象，且他俩没在一起，那么如果男孩子 \(A\) 相对于自己现在的对象更喜欢女孩子 \(B'\) 的话，那他一定会在表白自己当前的对象之前就表白了女孩子 \(A\)，但是被女孩子 \(A\) 拒绝了，说明女孩子 \(A\) 有更喜欢的男孩子了，此时不满足不稳定关系的定义，故所有关系一定是稳定的。

时间复杂度

最优 \(O(n)\)，最坏 \(O(n^2)\)。

最优情况下，在第一轮中，每个男孩子都没有被拒绝，直接一轮 \(O(n)\) 搞定。

最劣情况下，每一轮中都至少有一个女孩子和男孩子在一起，所以最多进行 \(n\) 轮，时间复杂度 \(O(n^2)\)。

注：最劣情况下的证明不严谨，但我不想写了，还要去补今天的第四题，各位可以自行证明。