/**
题目: Ladies' Choice UVALive - 3989
链接:https://vjudge.net/problem/UVALive-3989
题意:稳定婚姻问题
思路:
gale_shapley算法,参考文档:https://wenku.baidu.com/view/7aa841f2fab069dc502201cb.html */ #include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN = ;
const int INF = 0x3f3f3f3f; int blove[MAXN][MAXN];///存储女生编号 排在前面的女生编号越喜欢 !!!和glove[][]是不同的。
int glove[MAXN][MAXN];///表示第i个女生对第j个男生的的好感度 数值越大越喜欢
int boy[MAXN];///男生当前选择的女生。如果为-1,表示还没有选择。
int girl[MAXN];///女生当前选择的男生。如果为-1,表示还没有选择。
int boyrank[MAXN];///维护男生最中意的女生编号(排除已经拒绝他的女生之后)初始为1表示最喜欢最前面的那一个。
int N; void gale_shapley()///稳定婚姻问题 男生主动找女生 男生找的是最喜欢的,女生找的是稳定的最差的。交换数据可以反之。
{
memset(girl, -, sizeof girl);
memset(boy, -, sizeof boy);
for(int i = ; i <= N; i++) boyrank[i] = ;
int cnt = ;
while(cnt<N){///当cnt==N表示N个男生都选好了。
cnt = ;
for(int i = ; i <= N; i++){///所有男生向自己最中意的女生表白。
if(boy[i]!=-){
cnt++;
continue;///该男生已经选好了。暂时不用再选。
} int bestgirl = blove[i][boyrank[i]]; if(girl[bestgirl]==-){///该女生没有选择别人。
girl[bestgirl] = i;
boy[i] = bestgirl;
}else
{
if(glove[bestgirl][i]>glove[bestgirl][girl[bestgirl]]){
boyrank[girl[bestgirl]]++;///该女生找到更好的,被抛弃的男的要重新选择。更新男生最中意的女生。
boy[girl[bestgirl]] = -;///被抛弃的男生没有选择的女生了。
girl[bestgirl] = i;
boy[i] = bestgirl;
}else///女生坚持自己已经选过的,当前男生被拒绝。
{
boyrank[i]++;
}
}
}
}
}
int main()
{
int T, n;
cin>>T;
while(T--)
{
scanf("%d",&n);
N = n;
int x;
for(int i = ; i <= N; i++){
for(int j = ; j <= N; j++){
scanf("%d",&x);
blove[i][j] = x;
}
}
for(int i = ; i <= N; i++){
for(int j = ; j <= N; j++){
scanf("%d",&x);
glove[i][x] = N-j;
}
}
gale_shapley();
for(int i = ; i <= N; i++){
printf("%d\n",boy[i]);
}
if(T>){
printf("\n");
}
}
return ;
}
模板:
const int MAXN = ;
const int INF = 0x3f3f3f3f; int blove[MAXN][MAXN];///存储女生编号 排在前面的女生编号越喜欢 !!!和glove[][]是不同的。
int glove[MAXN][MAXN];///表示第i个女生对第j个男生的的好感度 数值越大越喜欢
int boy[MAXN];///男生当前选择的女生编号。如果为-1,表示还没有选择。
int girl[MAXN];///女生当前选择的男生。如果为-1,表示还没有选择。
int boyrank[MAXN];///维护男生最中意的女生编号(排除已经拒绝他的女生之后)初始为1表示最喜欢最前面的那一个。
int N; void gale_shapley()///稳定婚姻问题 男生主动找女生 男生找的是最喜欢的,女生找的是稳定的最差的。交换数据可以反之。
{
memset(girl, -, sizeof girl);
memset(boy, -, sizeof boy);
for(int i = ; i <= N; i++) boyrank[i] = ;
int cnt = ;
while(cnt<N){///当cnt==N表示N个男生都选好了。
cnt = ;
for(int i = ; i <= N; i++){///所有男生向自己最中意的女生表白。
if(boy[i]!=-){
cnt++;
continue;///该男生已经选好了。暂时不用再选。
} int bestgirl = blove[i][boyrank[i]]; if(girl[bestgirl]==-){///该女生没有选择别人。
girl[bestgirl] = i;
boy[i] = bestgirl;
}else
{
if(glove[bestgirl][i]>glove[bestgirl][girl[bestgirl]]){
boyrank[girl[bestgirl]]++;///该女生找到更好的,被抛弃的男的要重新选择。更新男生最中意的女生。
boy[girl[bestgirl]] = -;///被抛弃的男生没有选择的女生了。
girl[bestgirl] = i;
boy[i] = bestgirl;
}else///女生坚持自己已经选过的,当前男生被拒绝。
{
boyrank[i]++;
}
}
}
}
}