稳定婚姻问题
主要就是处理两个数组
boy[i][j] 存放第i个男的第j喜欢的女的 存的是女的编号!!
girl[i][j] 存放 第i个女的对第j个男的的好感度 存的是值
然后只要模板就行了
这题的数据处理有点麻烦 多学习!
#include<bits/stdc++.h>
using namespace std;
#define N 1000
int rank1[N];
int match_boy[N],match_girl[N];
double boy[N][N],girl[N][N];
int n; struct node
{
int cap,idx;
double x,y,z;
}lau[N],acc[N]; struct ode
{
int idx,cap;
double len;
}aim[N]; bool cmp(ode a,ode b)
{
if( fabs(a.len-b.len)<0.000001 )return a.cap>b.cap;
else return a.len<b.len;
} int main()
{
int cas;cin>>cas;
while(cas--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d %d %lf %lf %lf",&lau[i].idx,&lau[i].cap,&lau[i].x,&lau[i].y,&lau[i].z);
for(int i=;i<=n;i++)
scanf("%d %d %lf %lf %lf",&acc[i].idx,&acc[i].cap,&acc[i].x,&acc[i].y,&acc[i].z); for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
aim[j].len = sqrt((lau[i].x-acc[j].x)*(lau[i].x-acc[j].x) + (lau[i].y-acc[j].y)*(lau[i].y-acc[j].y) + (lau[i].z-acc[j].z)*(lau[i].z-acc[j].z));
aim[j].cap = acc[j].cap;
aim[j].idx = acc[j].idx;
} sort(aim+,aim++n,cmp);//求第i个男的对所有的女的好感排序 for(int j=;j<=n;j++)
boy[i][j]=aim[j].idx;//放置第i个男的第j喜欢的女的是谁! } for(int i=;i<=n;i++)
{ for(int j=;j<=n;j++)
{
aim[j].len = sqrt((acc[i].x-lau[j].x)*(acc[i].x-lau[j].x) + (acc[i].y-lau[j].y)*(acc[i].y-lau[j].y) + (acc[i].z-lau[j].z)*(acc[i].z-lau[j].z));
aim[j].cap = lau[j].cap;
aim[j].idx = lau[j].idx;
}
sort(aim+,aim++n,cmp);
for(int j=;j<=n;j++)
girl[ acc[i].idx ][ aim[j].idx ]=n-j;//放置第i个女的对第j个男的的好感度! 不需要放len 直接n-j就行
} //处理好boy和girl数组 其他的完全一样! int flag=;
memset(match_boy,,sizeof match_boy);
memset(match_girl,,sizeof match_girl);
memset(rank1,,sizeof rank1); while(flag)
{
flag=;
for(int i=;i<=n;i++)
{
if(!match_boy[i])
{
int temp=boy[i][rank1[i]++];
if(!match_girl[temp])
match_boy[i]=temp,match_girl[temp]=i;
else if( girl[temp][i]>girl[temp][match_girl[temp]] )
{
match_boy[ match_girl[temp] ]=;
match_boy[i]=temp;
match_girl[temp]=i;
}
flag=;
}
}
} for(int i=;i<=n;i++)
cout<<i<<' '<<match_boy[i]<<endl;
cout<<endl;
}
return ;
}