< 题目链接 >
题目大意:
给你 N 个男生和 N 个女生, 并且给出所有男生和女生对其它所有异性的喜欢程度, 喜欢程度越高的两个异性越容易配对, 现在求出它们之间的稳定匹配.
解题分析:
稳定婚姻问题的模板题, 需要用到 Gale_Shapley 算法, GS 算法讲解 >>>
这个算法还是很直观的.
- #include <iostream>
- #include <cstring>
- #include <stack>
- #include <string>
- #include <map>
- #include <algorithm>
- using namespace std;
- #define N 505
- #define clr(a,b) memset(a,b,sizeof(a))
- #define rep(i,s,t) for(int i=s;i<=t;i++)
- int n,getmp_boy[N][N],getmp_girl[N][N],boy[N],girl[N],rnk[N];
- map<string,int>mp_boy,mp_girl;
- string s,name_boy[N],name_girl[N];
- void Gale_Shapley(){
- clr(boy,0);clr(girl,0);
- rep(i,1,n) rnk[i]=1;
- while(true){
- bool flag=false;
- rep(i,1,n){
- if(!boy[i]){
- int x=getmp_boy[i][rnk[i]++]; //x 为当前男生所最求的他没有尝试最求过的最喜欢的女生
- if(!girl[x]){ // 如果这个女生没有和男生配对
- boy[i]=x; // 那么这对男女进行配对
- girl[x]=i;
- }else if(getmp_girl[x][i]> getmp_girl[x][girl[x]]){ // 如果当前女生已经配对, 那么就判断她对这两个男生的喜欢程度
- boy[girl[x]]=0; // 将原来的男生抛弃
- girl[x]=i; // 将这两个男女进行配对
- boy[i]=x;
- }
- flag=true;
- }
- }
- if(!flag)break; // 如果所有男生都已配对, 则直接退出
- }
- rep(i,1,n) cout<<name_boy[i]<<" "<<name_girl[boy[i]]<<endl;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- while(cin>>n){
- mp_boy.clear();mp_girl.clear();
- int pos=1,tmp;
- rep(i,1,n){
- cin>>s;name_boy[i]=s;
- mp_boy[s]=i;
- rep(j,1,n){
- cin>>s;tmp=mp_girl[s];
- if(!tmp){ // 对于之前没有出现过个的女生姓名, 重新分配序号
- tmp=pos++;
- mp_girl[s]=tmp;
- name_girl[tmp]=s;
- }
- getmp_boy[i][j]=tmp; // 记录第 i 个男生第 j 个喜欢的女生是 tmp
- }
- }
- rep(i,1,n){
- cin>>s;int x=mp_girl[s];
- rep(j,1,n){
- cin>>s;int y=mp_boy[s];
- getmp_girl[x][y]=n-j; // 记录第 i 个女生喜欢男生 y 的程度是 n-j
- }
- }
- Gale_Shapley();
- }
- }
- 2019-01-17
来源: http://www.bubuko.com/infodetail-2923523.html