n个男生和m个女生进行配对，一个男生匹配且仅能匹配一个女生，一个女生同样匹配且匹配一个男生。每个男生对n个女生都有一个好感值（不存在一个男生对两个女生好感值相同的情况），同样每个女生对n个男生也有一个好感值（也不存在一个女生对两个男生好感值相同的情况）。
现在求出一种匹配，该种匹配具有如下性质：
不存在一男A，一女B它们不匹配，但相比于他们现在的匹配对象A‘、B‘，A更愿意和B匹配且B也更愿意与A匹配，即A对B的好感度大于A‘，且B对A的好感度大于B‘。
一个特殊的二部图<X,Y,E>;X、Y都为点集，X、Y互不相交，X中的点数=N，Y中的点数=M，且X、Y互补相邻，即不存在X部的点和Y部的点相邻；E为有向带权边，任意X部的点都向Y部的点连接一条有向边，任意Y部的点都向X部的点连接一条有向边，也就是说图中共有N*(M-1)+M*(N-1)条有向带权边。
定义稳定匹配集：W为E的子集，W中共有2*min(N,M)条有向边，且若A->B属于W，则B->A同样属于W；若A->B属于W，且A->C也属于W，则B=C，且W满足:
任取A属于X，B属于Y，记A->A‘属于W，B->B‘属于W，不存在 A->B的权值大于A->A‘且B->A的权值大于B->B‘的情况。
X部的每个点都向它的好感值（即权值）最高的Y部的点发出邀请，然后Y部点的从其所收到的点中选取自身好感度(权值)最高点匹配，即一个Y部的点可能受到多个邀请，这时她选择自己最感兴趣的，其余的退回。
X部没有匹配上的点向它的好感值第二高的Y部的点发出邀请，然后Y部的点更新自身的匹配点为对自身来说更好的点。
重复此过程，X部点不断降低自身要求。
最多重复M-1次即可达到稳定状态。假设M>=N,匹配M轮后存在一个A∈X，A未匹配，因为现在A已经尝试和M个女生匹配过了，且最终都是被拒绝，或者被更高的顶替掉了，这说明此时M个女生都匹配了，又M>=N，所以矛盾。
定理：二分图模型中稳定匹配一定存在。
性质：
1、在一轮轮的匹配过程中，X部点的匹配结果不断降低，Y部点的匹配结果不断上升，换句话说X部点的期望逐渐降低，Y部点的期望逐渐升高。
2、稳定匹配存在多种可能，Gale-Shapley算法求出的只是其中一种。若以X部为发出邀请部，最终得到的匹配结果在所有匹配结果中对X部是最有利的；相反若以Y部为发出邀请部，则最终结果对Y部最有利。
扩展：该算法在一对多的时候也适用，即X部可以匹配多个或者Y部可以匹配多个,但当X部和Y部同时可以匹配多个点的时候不适用。
假设Y部点可以匹配多个点。则以X部点作为发出邀请方，Y部点在接收邀请时，检测是否能优化自身目前的选择，（优化：将一个好感度比当前邀请低的舍弃，使得整体的好感度上升）。
资料：http://www.icourses.cn/web/sword/portal/shareDetails?cId=3271#/course/chapter 第四章 时间：39：30 PS：这个老师讲的更加通俗易懂
实现个锤子，没空。
原文：https://www.cnblogs.com/dialectics/p/12373814.html