## 2018 年 08 月 28 日 • 阅读: 918 • 图论 • 阅读设置

• 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

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

### Source

Southwestern Europe 2007

### 链接

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

——转载自：传送门，总结的不错。

### 代码

StatusAccepted
Time190ms
Length1782
#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 星期二