学校招收学生 优先级按照： 分数 是否本地 志愿先后
相当于 女的开后宫
对gs进行略微修改
结束的条件为每个男的表白完所有女的
第二部分比较时 找出女的后宫里的吸引力最弱的男的比较 然后是否取代
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200
#define eps 1e-6
using namespace std;
struct node
{
int id,region,score,k;
}stu[N];
struct node1
{
int region,num;
}sch[N];
struct node2
{
int cnt;
int manname[N];
}woman[N];
int r,n,m;
int map1[N][N],map2[N][N],man[N],times[N],vis[N];
int cmp(node a,node b)
{
if(a.region==r)
{
if(b.region==r)
return a.score>b.score;
if(b.region!=r)
{
if(abs(a.score-0.7*b.score)<eps)
return ;
else
return a.score>0.7*b.score;
}
}
else if(b.region==r)
{
if(a.region==r)
return a.score>b.score;
if(a.region!=r)
{
if(abs(b.score-0.7*a.score)<eps)
return ;
else
return b.score<0.7*a.score;
}
}
else
return a.score>b.score;
}
int cmp1(node a,node b)
{
return a.id<b.id;
}
void makerank()
{
int i,j;
for(i=;i<=m;i++)
{
r=sch[i].region;
sort(stu+,stu+n+,cmp);
for(j=;j<=n;j++)
map2[i][stu[j].id]=j;
}
sort(stu+,stu+n+,cmp1);
}
void Gale_Shapley()
{
int flag=,i,j,worstrank,worstrankj;
memset(man,,sizeof(man));
for(i=;i<=n;i++)
times[i]=;
for(i=;i<=n;i++)
vis[i]=;
for(i=;i<=m;i++)
woman[i].cnt=;
while(flag)
{
flag=;
for(i=;i<=n;i++)
{
while(!man[i]&&!vis[i])
{
flag=;
if(times[i]>stu[i].k)
{
vis[i]=;
break;
}
int name=map1[i][times[i]];
if(woman[name].cnt<sch[name].num)
{
woman[name].manname[++woman[name].cnt]=i;
man[i]=name;
times[i]++;
}
else if(woman[name].cnt==sch[name].num)
{
worstrank=;
for(j=;j<=woman[name].cnt;j++)
{
if(map2[name][woman[name].manname[j]]>worstrank)
{
worstrank=map2[name][woman[name].manname[j]];
worstrankj=j;
}
}
if(map2[name][i]<worstrank)
{
man[woman[name].manname[worstrankj]]=;
woman[name].manname[worstrankj]=i;
man[i]=name;
times[i]++;
}
else
times[i]++;
}
}
}
}
}
int main()
{
int T,j,i;
scanf("%d",&T);
while(T--)
{
memset(map1,,sizeof(map1));
memset(map2,,sizeof(map2));
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
{
stu[i].id=i;
scanf("%d%d%d",&stu[i].region,&stu[i].score,&stu[i].k);
for(j=;j<=stu[i].k;j++)
{
scanf("%d",&map1[i][j]);
}
}
for(i=;i<=m;i++)
{
scanf("%d%d",&sch[i].region,&sch[i].num);
}
makerank();
Gale_Shapley();
for(i=;i<=n;i++)
if(vis[i])
printf("not accepted\n");
else
printf("%d\n",man[i]);
if(T) printf("\n");
}
return ;
}