LightOJ - 1400 Employment(婚姻稳定问题)

题目大意：在一个party上，有N个男的，N个女的，要求你将其配对，使其满足
1.男生u和女生v还没配对
2.他们喜欢对方的程度都大于喜欢各自当前舞伴的程度
如果出现了2的情况，他们就会抛下当前的舞伴，另外组成一对

解题思路：这题的话，就是婚姻稳定问题，他的解决方法是，男士不断的求婚，而女士不断的拒绝，直到男生找到合适的女生

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 210;
int n, cas = 1;
//No[i][j]表示j在i心中的排名
//pre[i][j]表示第i个人心中，第j的排名是谁

int Next[N], No[N][N], pre[N][N];
int future_husband[N], future_wife[N];

void init() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &pre[i][j]);
            No[i][pre[i][j]] = j;
        }
        Next[i] = 1;
    }

    for (int i = n + 1; i <= 2 * n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &pre[i][j]);
            No[i][pre[i][j]] = j;
        }
}

void solve() {
    memset(future_husband, 0, sizeof(future_husband));
    memset(future_wife, 0, sizeof(future_wife));
    queue<int> Q;
    //男生发出请求
    for (int i = 1; i <= n; i++) Q.push(i);

    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        int v = pre[u][Next[u]++];

        //如果女生没有舞伴
        if (!future_husband[v]) {
            future_husband[v] = u;
            future_wife[u] = v;
        }//如果女生有舞伴，但符合第二种情况
        else if (No[v][future_husband[v]] > No[v][u]) {
            Q.push(future_husband[v]);
            future_husband[v] = u;
            future_wife[u] = v;
        }//被拒绝了
        else Q.push(u);
    }
    printf("Case %d:", cas++);
    for (int i = 1; i <= n; i++)
        printf(" (%d %d)", i, future_wife[i]);
    printf("\n");
}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}