U97799 稳定匹配
  • 板块学术版
  • 楼主夸克味变
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/12 21:57
  • 上次更新2023/10/23 21:42:39
查看原帖
U97799 稳定匹配
156058
夸克味变楼主2023/3/12 21:57

请各位大佬帮我看看 我的这个代码 为啥一直WA啊 绝望.jpg

#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;
}

2023/3/12 21:57
加载中...