也谈恋爱中的问题

    当日遇到月，于是有了明。当我遇到了你，便成了侣。
    那天，日月相会，我见到了你。而且，大地失去了光辉，你我是否成侣？

    看到知乎上有个问题：恋爱中有哪些博弈？ 感觉是个非常有意思的问题，作为一个入坑一年的ACMer弱菜，也想写写自己见过的关于恋爱的问题。

声明：本文纯属娱乐，无亵渎爱情这一人生中最美好的情感之意。这里先祝有情人终成眷属。

Problem1：

(图片源自网络)

    在一个单身舞会上，有n个男生和m个妹子，如果某个妹子和某个男生之间两人互有好感，则两人可以一起去跳舞。那么最多可以凑成多少对去跳舞呢？

    基本概念和术语：这是一个二分图(或者叫二部图)的最大匹配问题。如果两人之间互有好感就在他们两个之间连一条边。一个匹配就是在所有的边中选一些边，使得选出来的这些边没有公共点(因为一个男生或者女生不可能同时和两个人跳舞)。而一个最大匹配就是尽可能多地选出一些符合这样要求的边。

    匈牙利算法便是解决这一类问题的。算法的思想是这样的：先给每个男生找一个可以一起跳舞的妹子，如果某个男生喜欢的妹子中都有舞伴了，那么就想办法给他“腾”出一个妹子来。所谓的“腾”就是考虑之前已经选好舞伴的男生，让他换一个没有舞伴的妹子跳舞，也就是把他当前的舞伴“腾”出来给这个找不到舞伴的男生。这是一个递归的过程，保证了充分利用“妹子”这一稀缺资源。算法执行完的最终结果就是撮合了最多的舞伴。

    最后代码如下，该代码能在HDU2063 上AC：

匈牙利算法求最大匹配

    本题也可以用网络流中的最大流算法，具体做法就是：增加一个源点s和一个汇点t，从源点s到每个男生连接一条容量为1的弧，从每个妹子到汇点t也连接一条容量为1的弧，最大匹配的个数就是从源点到汇点的最大流。其实这两种算法的思想是一样的，本质上都是在找增广路径。由于网络流编写起来较复杂，所以这里用网络流显得杀鸡用牛刀。

上面的问题多少有些残酷，因为尽管找到了最大匹配，可能也还是有人脱不了单。下面考虑这个问题：

Problem2：

    这次是有n个男生和n个女生(太棒了，正好能凑成n对)，每个男生对每个妹子在心目中做一个排序，排序要分先后，不出现并列的情况。同样地，每个妹子也对每个男生在自己心目中有个排序。现在他们之间两两结合，确立了恋爱关系。我们说一个不稳定的恋爱关系是这样的：

1.男生A和妹子a是情侣

2.男生B和妹子b是情侣

3.和现女友a相比，男生A更喜欢妹子b

4.和现男友B相比，妹子b更喜欢男生A

     之所以说这样的恋爱关系是不稳定的，因为男生A和妹子b很容易抛弃各自现在的恋人，而A和b确立新的恋爱关系。

     所以就有了稳定恋爱算法(原名其实叫稳定婚姻算法或者延迟认可算法)，算法的过程是这样的：

(1) 每一个单身狗在尚未拒绝过她的妹子中选一个排名最靠前的妹子追

(2) 对于每个妹子来说，选一个追求她的人中，她心目中排名最靠前的男生答应他，然后拒绝其他人

代码相比上一个来说虽然长了点，但还是非常好懂，此代码可以在UVaLive3989上AC，代码要认真读哦，非常容易懂~：

稳定恋爱关系算法

虽然妹子们在追她的男生中挑来挑去，但是有个一乍一听不合常理的结论：

在这样一个男追女，女挑男的算法中，每个妹子最终的男朋友是所有稳定关系中是所有对她合适的恋人中排名最靠后的那个。

而对于男生们来说，他能得到所有稳定恋爱关系中排名最靠前的妹子。

限于篇幅，这里就不给出严格的证明了。但是可以这样想一下：在每个男生找到最终的恋人之前，他可以确定那些排名靠前的女神是不可能答应他的了，所以可以死心了，去追后面的妹子。但是对于妹子们来说，即使她可能拒绝过很多人，但是她喜欢的那个「傻逼」可能不怎么喜欢她。正所谓：多少红颜为傻逼，多少傻逼不珍惜。

由此也能得到一条结论：幸福是主动争取得来的，在爱情中也是如此。

Problem3:

在一个相亲晚会中，主办方决定安排安排这些单身男女在大厅共进晚餐，交流情感，增进关系。安排他们就坐的原则是这样的：大厅中有多个圆桌，每个桌子上男女相间围着桌子坐一圈。问要怎样安排才能让每个人对左右两边的异性都是有好感的。

我们可以建一个网络流模型，然后求一遍最大流来求得满足要求的方案。因为每个桌子上都是男女间，所以男生人数和妹子的数量是相等的，而且每个人左右两边都是有好感的异性。具体建模方法就是，如果两个人互有好感那就连一条容量为1的弧。然后增加一个源点和一个汇点，因为每个人两边都有人，所以从源点到每个男生连一条容量为2的弧，从每个妹子到汇点也连一条容量为2的弧。求一遍最大流，如果流量满载的话，说明有可行方案。

这是我自己YY出来的一道题目，不知道OJ上有没有这道题。

代码看起来可能是这个样子的：

Problem4:

好吧，假设你很不幸当了四年的单身狗，现在毕业以后走上了漫漫的相亲路。现在你去一家婚介公司登记了个人信息，然后符合条件而且愿意和你相亲妹子有n个。于是你打算和这些妹子们一个一个的约会。和前面一样，假设你能给你见过的每个妹子排个序，而且对每个妹子有不同的偏爱程度。

还有这样一条原则，在约会的过程中，对于每个妹子只有两个选择：

要么和她一直交往下去，不再和其他的妹子约会。

要么去和下一个妹子相亲，不再和这个联系，因为突然再回头去找她是很没有面子的。

那么，如何能找到你心目中排名最高的那个女神，概率又是多少呢？

最不经过大脑的方案：随便选一个。那这样和女神在一起的概率就是1/n.这显然并不是一个可行的方法。

把方案稍微改进一下：我们先放弃前一半相亲过的妹子，但仍要好好去交流情感，以做到「心中有数」。然后在后一半相亲的过程中如果遇到比前一半中排名更高妹子，就选择她交往下去。假设n = 2k 为偶数，那么这样的方法遇到女神的概率为

，相比上个方案已经高出很多了。

寻找最佳方案：放弃前面一半的妹子并不一定是最佳方案，那么最佳方案是放弃多少的妹子，然后从后面开始找排名更靠前的呢？

碍于智商不足，这里只能把结论告诉大家，如果想看详细的证明请戳这里 。

最终的结论就是在n不是特别小的时候(比如n≥10)，放弃前面的n/e个妹子(e为自然对数)，在后面的妹子中找排名最高的。这样遇到女神的概率为1/e ≈ 0.36

最后说一个简单的博弈论的题目，收尾好了。

Problem 5:

一天小明去图书馆找和博弈论有关的书籍，发现旁边有一个漂亮妹子也在看这类书。于是小明凑上去和妹子搭讪，两个人愉快地聊了起来，他们讨论了巴什博奕，尼姆博弈，威佐夫博奕等经典的博弈模型，最后小明认为时间成熟了：

小明：妹子，能告诉我你的手机号码？

妹子：我和你玩个游戏吧，赢了，我就把我的手机号告诉你。

小明：好啊，没问题！

妹子：我有一堆硬币，一共7枚，从这个硬币堆里取硬币，一次最少取2枚，最多4枚，如果剩下少于2枚就要一次取完。我和你轮流取，直到堆里的硬币取完，最后一次取硬币的算输。我玩过这个游戏好多次了，就让让你，让你先取吧~

小明心想：妹子最后一句的波浪线暗藏杀机(=_=||)，后来经过一番思考发现这是不可能赢的。于是说：还是mm优先啦，呵呵~

小明最后一句的波浪线给出了有力的回击。

妹子：小伙子，挺聪明的嘛。那我考考你，如果我这有n枚硬币，一次最少取p枚，最多取q枚，不足p枚必须直接取完，最后一次取得人输。问：何时先手有必胜策略？

妹子为了考验小明也真是拼，小明为了要到手机号更要拼。

最终小明还是要到了手机号，成功回答了这个问题：从n = 1开始，前p个状态是必败状态，后面q个状态是必胜状态，然后循环往复。

证明的思路很简单，主要是依据两个原则：

一个状态是必胜状态当且仅当有一个后继是必败状态

一个状态是必败状态当且仅当所有后继都是必胜状态

相信聪明的读者一定能自己证明出来的，=￣ω￣=

小结：

看了上面的内容你是否感觉收获良多，对爱情又有了新的理解？

然而

这并没有什么卵用。