请各位大佬帮我看看 我的这个代码 为啥一直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;
}