关键词：
一、问题
有N男N女，每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。
何为稳定？
有两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，
随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发生。
二、算法步骤描述：
第一轮，每个男人都选择自己名单上排在首位的女人，并向她表白。这种时候会出现两种情况：
（1）该女士还没有被男生追求过，则该女士接受该男生的请求。
（2）若该女生已经接受过其他男生的追求，那么该女生会将该男士与她的现任男友进行比较，若更喜欢她的男友，那么拒绝这个人的追求，否则，抛弃其男友（囧）……
第一轮结束后，有些男人已经有女朋友了，有些男人仍然是单身。
在第二轮追女行动中，每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个，并向她表白，不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况，还是同样的解决方案。直到所有人都不在是单身。
三、基于hdu1522题的模板与讲解
#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; }
hdu1914稳定婚姻匹配
TheStableMarriageProblemTimeLimit:5000/1000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):758 AcceptedSubmission(s):389ProblemDes 查看详情
uoj.41.[清华集训2014]矩阵变换(稳定婚姻)(代码片段)
题目链接稳定婚姻问题：有n个男生n个女生，每个男/女生对每个女/男生有一个不同的喜爱程度。给每个人选择配偶。若不存在x,y未匹配，且x喜欢y胜过喜欢x当前的配偶，y喜欢x也胜过y当前的配偶的完备匹配，则称这是一个稳定... 查看详情
图论-稳定婚姻问题
稳定婚姻问题“稳定婚姻问题”在生活中是一个典型的问题,通俗地可叙述为:当前有N位男生和N位女生最后要组成稳定的婚姻家庭,过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序.然后开始选择... 查看详情
hdu1522marriageisstable稳定婚姻匹配(模板题)(代码片段)
...欢程度越高的两个异性越容易配对，现在求出它们之间的稳定匹配。解题分析：稳定婚姻问题的模板题，需要用到Gale_Shapley算法，GS算法讲解 >>>这个算法还是很直观的。1#include<iostream>2#include<cstring>3#include<st... 查看详情
marriageisstablehdu1522稳定婚姻问题(代码片段)
...理的匹配要打印名字的话必须有一个名字数组英文名用map稳定婚姻问题：每次循环遍历所有的男的每个男的对目前未被拒绝的并且优先级最高的进行预匹配 如果1女的没有伴侣2女的对该男的好感度比女的伴侣的好感度更高&nbs... 查看详情
稳定婚姻（tarjan）(代码片段)
...个强连通分量中有多于1个点，那么就说明这个婚姻并不稳定（夫妻之间连单向边，所以如果婚姻稳定的话夫 查看详情
稳定婚姻问题(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 查看详情
结婚匹配问题
...是A更偏爱b而不是a，b更偏爱A而不是B。则这个婚姻就是不稳定的。A和b可能背着别人相伴而走。由于他俩都觉得，与当前配偶比起来他们更偏爱各自的新伴侣。假设完 查看详情
poj3487[稳定婚姻]
TheStableMarriageProblemTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 2974 Accepted: 1267DescriptionThestablemarriageproblemconsistsofmatchingmembersoftwodifferentsetsacco 查看详情
使用gale-shapley算法解决稳定婚姻问题(代码片段)
Gale-Shapley算法又叫做延迟认可算法，它可以解决这么一个问题一共有N位男士和N位女士每位男士对每位女士都有一个好感度，让他们结合成为N对夫妻，要求男士优先表白，最后问结合情况第一轮，每个男人都选择自己名单上排在... 查看详情
tarjanbzoj2140-稳定婚姻
又名NTR的故事【题目大意】n对夫妻Bi和Gi。若某男Bi与某女Gj曾经交往过，他们有私奔的可能性。不妨设Bi和Gj旧情复燃，进而Bj会联系上了他的初恋情人Gk，以此递推。若在Bi和Gi离婚的前提下，这2n个人最终依然能够结合成n对情侣... 查看详情
稳定婚姻模型(代码片段)
原文地址：https://blog.csdn.net/qq_33913037/article/details/71328099 假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中... 查看详情
bzoj2140:稳定婚姻图论-tarjan
【bzoj2140】:稳定婚姻哎。。都是模板题。。一眼看过去哇二分图哎然后发现好像并不能匈牙利算法自己xjb画两张图，发现二分图左向右连配偶的边，然后右向左连交往过的边然后如果BiGi在同一个强连通分量里面就一定可以在BiGi... 查看详情
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）感情出现问题时，他们有私奔的可能性... 查看详情
bzoj2140稳定婚姻（强联通分量判环）bzoj修复工程(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2140是hydro的BZOJ修复工程！（我也去领了一点题慢慢修着玩，这题就是我修... 查看详情
bzoj2140稳定婚姻（强联通分量判环）bzoj修复工程(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2140是hydro的BZOJ修复工程！（我也去领了一点题慢慢修着玩，这题就是我修... 查看详情