题目描述U97799 【模板】Stable Matching 稳定匹配问题

在大学校园内有 n 个男生和 n 个女生。每个男生心目中有他对每个女生喜欢程度的一个排列，每个女生心目中也有她对每个男生喜欢程度的一个排列。某一天，这些学生想要集体脱单，请你找到一个匹配方案，使得这个脱单计划是稳定的。

如果存在一个男生 i，他被匹配到的对象是女生 x，又存在一个女生 y，她被匹配到的对象是男生 j，然而在 i 心目中，他比起 x 更喜欢 y，在 y 心目中，她比起 j 更喜欢 i，那么这个匹配方案就是不稳定的，因为男生 i 和女生 y 可能会私奔。相反，没有出现不稳定情况的匹配方案是稳定的。

输入格式

第 1 行一个数 n。第 2 行至第 n+1 行，每行 n 个数，第 i+1 行表示第 i 个男生心目中对女生的喜爱程度排列。第 n+2 行至第 2n+1 行，每行 n 个数，第 n+i+1 行表示第 i 个女生心目中对男生的喜爱程度排列。

输出格式

共 n 行，表示一个稳定匹配的方案。第 i 行表示第 i 个女生匹配到的男生序号。方案可能有多种，你只需要给出一种方案即可

代码里是先输入女生，再输入男生 （因为一开始看错了qaq 但是这应该不影响结果）

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;


//女性最佳的稳定匹配 
void stable_matching(vector<vector<int> >girl, vector<vector<int> >boy ,vector<int> &boy_to_girl)
{
	int n = girl.size();
	
	//当前未匹配女生队列 
	queue<int> single_girl;
	for(int i=1;i<=n;i++)
	{
		single_girl.push(i);	
	} 

	while(!single_girl.empty())
	{
		int girl_id = single_girl.front();//当前待匹配的女生 
		
		for(int j=0;j<n;j++)
		{
			int boy_id = girl[girl_id-1][j]; //下标是序号减 1
			
			
			if(boy_to_girl[boy_id]==-1)//若女生的顺位男生未被匹配，直接予以匹配 
			{
				boy_to_girl[boy_id] = girl_id;
				single_girl.pop();
				break; 
			}
			else //若女生的顺位男生已被匹配，男生反选 
			{
				int pre_girl_id = boy_to_girl[boy_id]; 
				int flag=0;
				for(int k=0;k<n;k++)
				{
					if( boy[boy_id-1][k] == girl_id ) //现在的女生排在更前面，替换 
					{
						flag=1;
						break;
					}
					else if( boy[boy_id-1][k] == pre_girl_id) //之前的女生排在更前面，不替换 
					{
						break;
					} 
				}
				if(flag==1)
				{
					boy_to_girl[boy_id] = girl_id;
					single_girl.pop();
					single_girl.push(pre_girl_id);
					break;
				}
			}
		}
	}
	
}

int main()
{

	int n;
	cin>>n;
	vector<vector<int> > girl(n,vector<int>(n));//girl's preference 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>girl[i][j];
		}	
	}
	vector<vector<int> > boy(n,vector<int>(n));//boy's preference
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>boy[i][j];
		}	
	}

	// Gale-Shapley 算法
	vector<int> boy_to_girl(n+1,-1); //当前已匹配的男生和他匹配到的女生 
	stable_matching(girl,boy,boy_to_girl);
	
	//反转得到girl_to_boy 
	vector<int> girl_to_boy(n+1,0);
	for(int i=1;i<=n;i++)
	{
		girl_to_boy[ boy_to_girl[i] ] = i;
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<girl_to_boy[i]<<endl; 
	}

	return 0;
}