732 . 相親問題
TopCoder
Tags
Description
夏天到了！夏天，就是最適合戀愛的季節～～～
現在呢，你是相親活動的主辦活動，想要撮合 $N$ 位男生與 $N$ 位女生，各自皆從 $1$ 編號到 $N$。經過了許多輪的團康活動等等，你讓每個人都將異性依照喜好的程度排序 —— 是的，愛情是殘酷的。你想要找到一種將這 $2N$ 個人分成 $N$ 對男女，而且為了要儘量讓這些男女找到幸福，不要讓有人的伴侶找去找其他人的伴侶玩這種尷尬的事情發生，還必須滿足這個條件：
- 對於任何兩個異性且目前不是一對的人，他們不會兩個都想要換伴侶成對方（也就是兩個對於對方的好感比目前的伴侶都高）。
請幫忙解決這個問題吧！
Input Format
輸入有 $2N + 1$ 行。第一行是一個數字 $N(1 \leq N \leq 800)$，代表有幾個男生與女生。接下來的 $N$ 行的第 $i$ 行中的第 $j$ 個數字 $s_{ij}$ 代表編號為 $i$ 的男生第 $j$ 心儀的女生。然後也會有 $N$ 行，其中第 $i$ 行中的第 $j$ 個數字 $t_{ij}$ 代表編號為 $i$ 的女生第 $j$ 喜歡的男生。
保證所有的資料皆合法，不會出現範圍外的數字與重複的排名。
Output Format
如果有解，請輸出 $N$ 個數字，第 $i$ 個數字 $x_i$ 代表編號為 $i$ 的男生應該要和編號為 $x_i$ 的女生配對。如果無論如何都無法滿足條件，請輸出 -1。倘若有多組解，輸出任意一者即可。
Sample Input 1
3
2 1 3
3 2 1
1 3 2
2 1 3
3 2 1
1 3 2
2 1 3
3 2 1
1 3 2
2 1 3
3 2 1
1 3 2
Sample Output 1
2 3 1
Sample Input 2
2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
1 2
Sample Output 2
2 1
Sample Input 3
2
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1
Sample Output 3
1 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~12 | 無額外限制 | 100 |