关键词：
稳定婚姻问题
“稳定婚姻问题”在生活中是一个典型的问题,通俗地可叙述为:当前有N位男生和N位女生最后要组成稳定的婚姻家庭,过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序.然后开始选择自己的对象,其规则是:男生第一天均向各自最喜欢的女生写一封“情书”。
问题来源
问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。
对于典型“稳定婚姻问题”，借助矩阵(二维数组)给出了一种简明的实现方法。在本算法中，所采用的存储结构和实现方法灵活巧妙，通俗易懂，方便实现；而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半，空间复杂度为O(1)；由于存储结构的巧妙性，算法的时间复杂度在最好的情况下为线性时间N，在最坏的情况下为O(N2)。
这个是数学界切切实实研究过的问题。对于以前没有接触过这个问题的人，这个理论最出人意外的结论是:传统的求爱，结婚过程是male-optimal的，也就是说，男性能够得到尽可能好的心上人，女性却不然。这就是所谓的稳定匹配问题(StableMarriageProblem，也叫稳定婚姻问题）。
定理
稳定婚姻问题。它有很多种可能的解法。
为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？于是它就这样流传下来了。
有很多组合数学问题都可以如此这般的翻译为生活中的问题。比如著名的Hall定理：给定n个有限集合（其间可以有交集），如果其中任意m个集合的并集的元素个数都不小于m，那么一定存在n个不同的元素，使得它们正好依次存在于这n个集合之中。我相信没有人明白以上这是在说什么。可是它有一个很好的解释：把那n个集合想象成n个男生各自心仪的女孩子们（一般来说都不止一个），中间的那个条件是说，如果对于其中任意一部分男生，他们喜欢的女孩子的总数都不少于这组男生的人数（这个条件是必要的，否则就打起来了），那么总的说来一定存在一种办法给每个男生都分配一个女生恰好是他喜欢的。
活动方式
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
①每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
②每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
③若某男士被其女友抛弃，重新变成自由男。
在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。
这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。
求婚过程
第一天上午，所有的男人都向自己最爱的女人求婚，下午，每个女人看看自己有没有收到，收到了多少人的求婚，如果只收到一个男人的求婚，那么就和他订婚。如果收到多于一个男人的求婚，那么就和其中她最爱的那个男人订婚，同时把其他男人都锯掉。如果一个求婚都没有，不要着急，最后总会有的。晚上，检查一遍，如果所有女人都订婚了，，万事大吉，明天举行集体婚礼，但如果还有女人没有订婚，那么事情还没有完，第二天还得重复，第二天上午，所有还没订婚的男人向自己次爱的女人求婚(因为昨天已经被他们的最爱锯了)。下午，每个女人再看一遍自己收到订婚的情况，如果她已经订婚了，但是又有一个她更爱的男人来向她求婚，那就把原来那个锯掉，再和这个更爱的男人订婚；如果还没订婚，那就和第一天的下午的处理一样。晚上再检查一遍，如果还是有人没有订婚，那第三天再重复，第三天上午，所有没有订婚的男人，包括第一天订了第二天又被踹出来的，再向还没有锯过他的女人中他最爱的那个求婚如此周而复始，直到最后大家都订了婚，便一起结婚。
这么个过程数学上可以证明：
第一，这个过程会中止，也就是说，总有大家都订了婚的一天，不可能无限循环。
第二，中止后所有的婚姻是稳定婚姻。所谓不稳婚姻是说，比如说有两对夫妇M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的老公虽说是M2.但她更爱M1,这样的婚姻就是不稳婚姻,M1和F2理应结合,他们现在各自的婚姻都是错误.我们能证明的是,通过上面那个求婚过程,所有的婚姻都是稳定的,没有人犯错误。
第三,比较引人注目的是，这个过程是male-optimal的，男性能够获得尽可能好的伴侣，比如说最后有二十个女人拒绝了他，他仍然能够得到剩下的八十个女人中他最爱的那一个。
第四，更有甚者，这个过程是female-pessimal的,女人总是在可能的情况下被最不喜欢的人追上。这一点没有那么直观的理解，勉强要解释的话，可以这么看:虽说女人每换一次订婚对象，都往上升一层，但起点可能很低，虽说在一步步接近她最爱的目标，但最后往往达不到。比如说还差三十名就达到她最爱的人了，但这时GameOver，所有的人都已订了婚，这样她也只能死了心了。还有三十个她更爱的人还没向她求过婚，可是她也无可奈何了，但她仍然能够得到剩下的七十个男人中她最爱的那一个。
图论算法：稳定婚姻问题，如何找到最适合自己的另一半
什么是算法？每当有人问我这样的问题，我总会引用下面这个例子。假如你是一个媒人，有若干名单身男子登门求助，还有同样多的单身女子也来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名，... 查看详情
每日一书丨图论算法：稳定婚姻问题，如何找到最适合自己的另一半
什么是算法？每当有人问我这样的问题，我总会引用下面这个例子。 假如你是一个媒人，有若干名单身男子登门求助，还有同样多的单身女子也来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名ÿ... 查看详情
稳定婚姻匹配问题
...安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。 何为稳定？ 有两对夫妻M1F2，M2F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的， ... 查看详情
稳定婚姻问题(stablemarriageproblem)
转自http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html稳定婚姻是组合数学里面的一个问题。问题大概是这样：有一个社团里有n个女生和n个男生，每位女生按照她的偏爱程度将男生排序，同时每位男生也按照自己的偏爱程度将... 查看详情
模板：稳定婚姻问题(代码片段)
1#include<bits/stdc++.h>2usingnamespacestd;34constintN=234;56intRank[N][N];//i,j第i个人心中,第j排名是谁7intM[N][N];//i,jj在i心中的排名8intboy[N],girl[N],Next[N];9intn,t;1011voidsolve()12memset(boy,0,sizeof(boy 查看详情
图论８月１９日前填坑指南（自用）
Graph图论前向星图的割点、桥双连通分量有向图的强连通分量无向图连通分支拓扑排序2-SAT最短路第K短路哈密顿路、欧拉路径、欧拉回路DAG的深度优先搜索标记独立集、团、支配集概念最大团问题弦图判断弦图的PERFECTELIMINATION点... 查看详情
稳定婚姻匹配问题(代码片段)
假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名(1)，你应该怎样为他们牵线配对呢？ ... 查看详情
poj3487[稳定婚姻]
TheStableMarriageProblemTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 2974 Accepted: 1267DescriptionThestablemarriageproblemconsistsofmatchingmembersoftwodifferentsetsacco 查看详情
稳定婚姻（tarjan）(代码片段)
...个强连通分量中有多于1个点，那么就说明这个婚姻并不稳定（夫妻之间连单向边，所以如果婚姻稳定的话夫 查看详情
uoj.41.[清华集训2014]矩阵变换(稳定婚姻)(代码片段)
题目链接稳定婚姻问题：有n个男生n个女生，每个男/女生对每个女/男生有一个不同的喜爱程度。给每个人选择配偶。若不存在x,y未匹配，且x喜欢y胜过喜欢x当前的配偶，y喜欢x也胜过y当前的配偶的完备匹配，则称这是一个稳定... 查看详情
使用gale-shapley算法解决稳定婚姻问题(代码片段)
Gale-Shapley算法又叫做延迟认可算法，它可以解决这么一个问题一共有N位男士和N位女士每位男士对每位女士都有一个好感度，让他们结合成为N对夫妻，要求男士优先表白，最后问结合情况第一轮，每个男人都选择自己名单上排在... 查看详情
hdu1914稳定婚姻匹配
TheStableMarriageProblemTimeLimit:5000/1000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):758 AcceptedSubmission(s):389ProblemDes 查看详情
tarjanbzoj2140-稳定婚姻
又名NTR的故事【题目大意】n对夫妻Bi和Gi。若某男Bi与某女Gj曾经交往过，他们有私奔的可能性。不妨设Bi和Gj旧情复燃，进而Bj会联系上了他的初恋情人Gk，以此递推。若在Bi和Gi离婚的前提下，这2n个人最终依然能够结合成n对情侣... 查看详情
marriageisstablehdu1522稳定婚姻问题(代码片段)
...理的匹配要打印名字的话必须有一个名字数组英文名用map稳定婚姻问题：每次循环遍历所有的男的每个男的对目前未被拒绝的并且优先级最高的进行预匹配 如果1女的没有伴侣2女的对该男的好感度比女的伴侣的好感度更高&nbs... 查看详情
稳定婚姻模型(代码片段)
原文地址：https://blog.csdn.net/qq_33913037/article/details/71328099 假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中... 查看详情
luogup1407[国家集训队]稳定婚姻(代码片段)
...$tarjan$，如果对于一对夫妻在强连通分量里，那么就是不稳定的，因为他们可以绕一圈。 #include<iostream>#include<cstdio>#include<cstring>#include<string>#include<map& 查看详情
51nod2903稳定婚姻(tarjan)(代码片段)
Problem我们已知n对夫妻的婚姻状况，称第i对夫妻的男方为Bi，女方为Gi。若某男Bi与某女Gj曾经交往过（无论是大学，高中，亦或是幼儿园阶段，i≠j），则当某方与其配偶（即Bi与Gi或Bj与Gj）感情出现问题时，他们有私奔的可能性... 查看详情
hdu1522marriageisstable稳定婚姻匹配(模板题)(代码片段)
...欢程度越高的两个异性越容易配对，现在求出它们之间的稳定匹配。解题分析：稳定婚姻问题的模板题，需要用到Gale_Shapley算法，GS算法讲解 >>>这个算法还是很直观的。1#include<iostream>2#include<cstring>3#include<st... 查看详情