1962 年，美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略。不管男女各有多少人，不管他们各自的偏好如何，应用这种策略后总能得到一个稳定的婚姻搭配。换句话说，他们证明了稳定的婚姻搭配总是存在的。有趣的是，这种策略反映了现实生活中的很多真实情况。
两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发生。
稳定婚姻是组合数学里面的一个问题。
问题大概是这样：有一个社团里有n个女生和n个男生，每位女生按照她的偏爱程度将男生排序，同时每位男生也按照自己的偏爱程度将女生排序。然后将这n个女生和n个男生配成完备婚姻。
如果存在两位女生A和B，两位男生a和b，使得A和a结婚，B和b结婚，但是A更偏爱b而不是a，b更偏爱A而不是B，则这个婚姻就是不稳定的，A和b可能背着别人相伴而走，因为他俩都认为，与当前配偶比起来他们更偏爱各自的新伴侣。
如果完备婚姻不是不稳定的，则称其是稳定的。通过证明，可以得到每一个n女n男的社团，都存在稳定婚姻的结论。但是这种情况只在异性的社团中存在。也就是说在同性的社团里面，稳定婚姻的存在性将不再被保证。
解决思路如下
首先选择一个单身男生，他会按照他的喜欢程度对一个还没有表白过的女生表白。
如果女生此时处于单身状态，则恭喜，他们两人将进入约会状态。
如果女生已经有男朋友，则女生会比较当前男朋友与表白的男生，如果更喜欢表白的男生，则恭喜，男生成功上位，女生之间的男朋友则进入单身状态；若女生还是更喜欢自己的男朋友，则不好意思，男生表白失败。
当所有的男生都脱离单身状态时，此时的约会状态应是稳定的，证明如下：
若存在之前描述的不稳定因素，即虽然男生i和女生a牵手，但男生i对女生b更喜欢，而女生b发现，相比自己的男朋友j，她更喜欢男生i。既然男生i更喜欢女生b，那么男生i肯定在对女生b表白失败之后才会对女生a表白，而若男生i对女生b的表白失败，则女生b至少有比对男生i更喜欢的男朋友，所以女生b相比自己的男朋友j更喜欢男生i并不成立，所以此时所有的约会状态都是稳定的。
可以从两个方面来证明该算法的正确性
1）一定不会出现最后仍有单身的情况（即保证有解），若一名男子到最后仍为单身，那么前提就是他已经追求了所有的女子，其中一定包括那名单身女子，而女子一旦被追求过了就不会再单身，这样的话就一定不存在一名女子和这名单身男子相配了，这显然是不符合实际的
2）这样的解一定是最优的：男子的配偶越来越差，而相反的女子的配偶越来越好，并且女子交换配偶一定是当她认为当前的男子更好的时候，也就是说两人结为配偶时一定是“认为彼此就是最适合的”才会结为配偶
以上就是Gale-Shapley算法的的流程
如果我们研究一下这个算法的核心逻辑，会发现其实是对男生有优势的，虽然女生看起来有最终的选择权，但男生更有机会追求自己最心仪的对象，而女生只能被动地等待男生发起追求来进行挑选。如果某个女生喜欢的男生不选她，那么她永远没有和他在一起的机会。这个故事告诉我们，喜欢的对象要自己挑，主动才是王道。
代码实现（为了更容易让人理解，找了份注释清晰的代码）
#include <iostream> #include <cstring> #include <stack> #include <map> using namespace std; int n,gp_boy[505][505],gp_girl[505][505],boy[505],girl[505],rank[505]; map<string,int>mp_boy,mp_girl; string sboy[505],sgirl[505]; char s[1000]; void Gale_Shapley() { memset(boy,0,sizeof(boy));///假设所有人是单身狗 memset(girl,0,sizeof(girl)); for(int i=1;i<=n;i++) rank[i]=1; while(1) { int flag=0; for(int i=1;i<=n;i++)///男生们开始追女生 { if(!boy[i])///如果男生是单身狗 { int g=gp_boy[i][rank[i]++];///开始最第一喜欢的女生 if(!girl[g])///如果女生恰好没有对象 { boy[i]=g;///在一起~ girl[g]=i; } else if(gp_girl[g][i]>gp_girl[g][girl[g]])///如果女孩孩子有对象但是比起对象更稀罕这个男生 { boy[girl[g]]=0;///原来的甩掉！！ girl[g]=i; boy[i]=g; } flag=1; } } if(!flag) break; } for(int i=1;i<=n;i++) { cout<<sboy[i]<<" "<<sgirl[boy[i]]<<endl; } } int main() { while(cin>>n)///n个男 n个女 { mp_boy.clear();///清空 mp_girl.clear(); int pos=1,tem; for(int i=1;i<=n;i++)///n个男生 { cin>>s; sboy[i]=s;///i号男生对应的名字 mp_boy[s]=i;///名字是s的男生对应的序号 for(int j=1;j<=n;j++) { cin>>s; ///男生喜欢的女生排名 tem=mp_girl[s];///看女生s的序号 if(tem==0)///如果序号是0 mp_girl[s]=tem=pos++;///给人家女孩子一个序号 sgirl[tem]=s;///序号tem的女生是s gp_boy[i][j]=tem;///所以第i号男生第j喜欢的女生的序号是tem } } for(int i=0;i<n;i++)///这时的我们看看女孩子喜欢的男生 { cin>>s; int x=mp_girl[s];///get到s女孩子的序号 for(int j=0;j<n;j++) { cin>>s; int y=mp_boy[s];///get到女孩第j个喜欢男孩子的序号 gp_girl[x][y]=n-j;///所以第x号女生喜欢y号男生的程度为n-j } } Gale_Shapley(); } return 0; }