UVA1175 Ladies' Choice（稳定婚姻问题）

Ladies' Choice

Time Limit: 5 Seconds
Memory Limit: 32768 KB

Teenagers from the local high school have asked you to help them with the organization of next year's Prom. The idea is to find a suitable date for everyone in the class in a fair and civilized way. So, they have organized a web site where all students, boys and girls, state their preferences among the class members, by ordering all the possible candidates. Your mission is to keep everyone as happy as possible. Assume that there are equal numbers of boys and girls.

Given a set of preferences, set up the blind dates such that there are no other two people of opposite sex who would both rather have each other than their current partners. Since it was decided that the Prom was Ladies' Choice, we want to produce the best possible choice for the girls.

Input

A positive integer P in a single line followed by a sequence of P test cases. Each test case consists of a positive integer N, not greater than 1,000, indicating the number of couples in the class. Next, there are N lines, each one containing the all the integers from 1 to N, ordered according to the girl's preferences. Next, there are N lines, each one containing all the integers from 1 to N, ordered according to the boy's preferences.

Output

The output consists of a sequence of N lines, where the i-th line contains the number of the boy assigned to the i-th girl (from 1 to N).

Sample Input

Sample Output

Source

Southwestern Europe 2007

链接

https://vjudge.net/problem/UVA-1175

题意

对于每个女生，在所有可能和她跳舞的男生中，找出她最喜欢的那个。

题解

著名的稳定婚姻问题，只是把“结婚”和“配偶”换成了“跳舞”和舞伴。
稳定婚姻问题就是给你n个男的，n个女的，然后给你每个男生中女生的排名，和女生心目中男生的排名，然后让你匹配成n对，使婚姻稳定，假如a和b匹配,c和d匹配，如果a认为d比b好，同时d也认为a比c好，那么ad就有可能私奔，这样就导致了婚姻的不稳定，稳定婚姻就是找到一种解决方案让婚姻稳定。
算法：稳定婚姻的解决方法比较简单，通俗易懂，而且还容易实现，具体有没有固定的模板我不知道，没有去找，自己模拟的，在求解的过程中，我们先把所有的男生都加到队列里，队列里的就表示当前还单身的男生，每次从队列里拿出一个男生，然后从她最喜欢的女生开始匹配，如果当前的女生尝试追求过，那么就不用追求了，如果当前的女生没有伴侣，那么可以直接匹配上，如果有伴侣，那么就看看当前这个男生和女生之前的伴侣在那个女生中更喜欢谁，如果更喜欢当前的这个男生，那么当前男生就和这个女生匹配，女生之前匹配过的直接变成单身，被扔回队列，否则，继续找下一个女生，知道找到一个能匹配上的为止，就这样一直到队列空的时候，就已经全部匹配完成了。
正确性：对于男生来说，每次都是从最喜欢的女生开始匹配的，遇到的第一个没人能抢走的并且稳定的就是自己最终伴侣，也就是说如果之前追求过的女生被别人抢走了，那么他将永远抢不会来，因为对于女生来说，第一次被男士按照自己的意愿选择之后，每次变更匹配对象都是在自己心目中更加喜欢的，所以一旦他放弃了某个男生，那么那个男生就没希望在和他匹配，这样男生是从最优的选的，保证男生不会出轨，女生每次都是在选择她的男生中选择最优的，这样也保证了女生最后没有怨言，这样的话，最后的到的婚姻就是稳定的，至于稳定婚姻，肯定会有稳定方案，这个我暂时证明不了，是看别人说的。
——转载自：传送门，总结的不错。

代码

因为本题是求解的女生心中最满意的男生，而板子写的是男生心中最满意的女生，所以刚好反过来，“男生变女生，女生变男生”，得到的就是答案，小蓝书上的板子。

Status	Accepted
Time	190ms
Length	1782

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1010;

int pref[maxn][maxn], order[maxn][maxn], Next[maxn];
int future_husband[maxn], future_wife[maxn];
int n;
queue <int> Q; // 未订婚男士队列

void engage(int man, int woman) // 订婚
{
    int m = future_husband[woman]; // 女士现任未婚夫m
    if (m) // 找到一个更爱她的，放弃原来的
    {
        future_wife[m] = 0; // m加入未订婚男士队列
        Q.push(m);
    }
    future_wife[man] = woman;
    future_husband[woman] = man;
}

void solve()
{
    while (!Q.empty())
    {
        int man = Q.front();
        Q.pop();
        int woman = pref[man][Next[man]++]; // 下一个求婚对象，从1开始
        if (!future_husband[woman]) // 女士没有未婚夫，直接订婚
            engage(man, woman);
        else if (order[woman][man] < order[woman][future_husband[woman]]) // 取代女士的现任未婚夫
            engage(man, woman);
        else // 丑拒，下次再来
            Q.push(man);
    }
    while (!Q.empty())
        Q.pop();
}

int main()
{
    int T, x;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
                scanf("%d", &pref[i][j]); // 编号为i的男士第j喜欢的人
            Next[i] = 1; // 接下来应该向排名为1的女士求婚
            future_wife[i] = 0; // 没有未婚妻
            Q.push(i);
        }
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                scanf("%d", &x);
                order[i][x] = j; // 在编号为i的女士心目中，编号为x的男士的排名
            }
            future_husband[i] = 0; // 没有未婚夫
        }
        solve();
        for (int i =1; i <= n; ++i)
            printf("%d\n", future_wife[i]);
        if (T)
            printf("\n");
    }
    return 0;
}

The end.
2018-08-28 星期二