Ladies' Choice

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
Input consists of multiple test cases the first line of the input contains the number of test cases.
There is a blank line before each dataset.
The input for each dataset consists of a positive integer N, not greater than 1,000, indicating the
number of couples in theclass. Next, there are N lines, each onecontaining 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 for each dataset consists of a sequence of N lines, where the i-th line containsthe number
of the boy assigned to the i-th girl (from 1 to N).
Print a blank line between datasets.
Sample Input
1
5
1 2 3 5 4
5 2 4 3 1
3 5 1 2 4
3 4 2 1 5
4 5 1 2 3
2 5 4 1 3
3 2 4 1 5
1 2 4 3 5
4 1 2 5 3
5 3 2 4 1
Sample Output
1
2
5
3
4

【题意】

　　有n对男女,先给出每个女生对n位男生的选择意向,排在前面的优先选择,然后给出n位男生的选择意向,排在前面的优先选择. 
　　输出每位女生的匹配,使得每位女生都是稳定的最佳选择.

【分析】

　　这是著名的稳定婚姻问题。

　　这题要求女士的最优选择，所以把男女反过来就好了。

2016-10-26 17:11:48

其实只要理解过程，代码是很好打的，来一个有解释的模版;

稳定婚姻问题：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

#define Maxn 1010

int ml[Maxn][Maxn],rk[Maxn][Maxn];

//ml[i][j]男士i心中排第j的女士是谁

//rk[i][j]女士i心中男士j排名第几

int fh[Maxn],fw[Maxn],nt[Maxn];

//fh[i]女士i的未婚夫 fw[i]男士i的未婚妻(若还没订婚则为0) nt[i]男士i下一次应该向谁求婚

queue<int > q;

void engage(int x,int y) //让男士x和女士y订婚 并且解除女士y之前的婚约（若有）

{

    int z=fh[y];

    if(z)

    {

        fw[z]=;

        q.push(z);

    }

    fw[x]=y;fh[y]=x;

}

int n;

void init()

{

        scanf("%d",&n);

        while(!q.empty()) q.pop();

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

             scanf("%d",&ml[i][j]);

            nt[i]=;

            fw[i]=;

            q.push(i);

        }

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                int x;

                scanf("%d",&x);

                rk[i][x]=j;

            }

            fh[i]=;

        }

}

void ffind()

{

    while(!q.empty())

    {

        int x=q.front();q.pop(); //未订婚男士求婚

        int y=ml[x][nt[x]++];

        if(fh[y]==||rk[y][x]<rk[y][fh[y]])

            engage(x,y);

        else q.push(x);//若求婚失败，则下次再来

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        init();

        ffind();

        for(int i=;i<=n;i++) printf("%d\n",fw[i]);//输出的是男士可能结婚的女士中最优的一个

        if(T) printf("\n");

    }

    return ;

}