Ladies' Choice UVALive

/**
题目: 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 = 1005;
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, -1, sizeof girl);
    memset(boy, -1, sizeof boy);
    for(int i = 1; i <= N; i++) boyrank[i] = 1;
    int cnt = 0;
    while(cnt<N){///当cnt==N表示N个男生都选好了。
        cnt = 0;
        for(int i = 1; i <= N; i++){///所有男生向自己最中意的女生表白。
            if(boy[i]!=-1){
                cnt++;
                continue;///该男生已经选好了。暂时不用再选。
            }

            int bestgirl = blove[i][boyrank[i]];

            if(girl[bestgirl]==-1){///该女生没有选择别人。
                girl[bestgirl] = i;
                boy[i] = bestgirl;
            }else
            {
                if(glove[bestgirl][i]>glove[bestgirl][girl[bestgirl]]){
                    boyrank[girl[bestgirl]]++;///该女生找到更好的，被抛弃的男的要重新选择。更新男生最中意的女生。
                    boy[girl[bestgirl]] = -1;///被抛弃的男生没有选择的女生了。
                    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 = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                scanf("%d",&x);
                blove[i][j] = x;
            }
        }
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                scanf("%d",&x);
                glove[i][x] = N-j;
            }
        }
        gale_shapley();
        for(int i = 1; i <= N; i++){
            printf("%d
",boy[i]);
        }
        if(T>0){
            printf("
");
        }
    }
    return 0;
}

模板：

const int MAXN = 1005;
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, -1, sizeof girl);
    memset(boy, -1, sizeof boy);
    for(int i = 1; i <= N; i++) boyrank[i] = 1;
    int cnt = 0;
    while(cnt<N){///当cnt==N表示N个男生都选好了。
        cnt = 0;
        for(int i = 1; i <= N; i++){///所有男生向自己最中意的女生表白。
            if(boy[i]!=-1){
                cnt++;
                continue;///该男生已经选好了。暂时不用再选。
            }

            int bestgirl = blove[i][boyrank[i]];

            if(girl[bestgirl]==-1){///该女生没有选择别人。
                girl[bestgirl] = i;
                boy[i] = bestgirl;
            }else
            {
                if(glove[bestgirl][i]>glove[bestgirl][girl[bestgirl]]){
                    boyrank[girl[bestgirl]]++;///该女生找到更好的，被抛弃的男的要重新选择。更新男生最中意的女生。
                    boy[girl[bestgirl]] = -1;///被抛弃的男生没有选择的女生了。
                    girl[bestgirl] = i;
                    boy[i] = bestgirl;
                }else///女生坚持自己已经选过的，当前男生被拒绝。
                {
                    boyrank[i]++;
                }
            }
        }
    }
}