| 题目名称 | 3248. [POJ 1904]King's Quest |
|---|---|
| 输入输出 | marriage_trouble.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 10 |
| 题目来源 |
 数声风笛ovo
于2019-11-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：3， 通过率：100% | ||||
 LGLJ |
100 | 0.096 s | 8.88 MiB | C++ |
|
LGLJ |
100 | 0.158 s | 7.40 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.160 s | 11.41 MiB | C++ |
| 关于 King's Quest 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数据已更新完成！
  数声风笛ovo
2019-10-22 21:31
4楼
| ||||
|
回复 @数声风笛离亭 :
好吧，没事 LGLJ
2019-10-22 20:49
3楼
| ||||
|
回复 @LGLJ :
对对对不起QWQ，数据还没粘完 数声风笛ovo
2019-10-22 20:48
2楼
| ||||
|
数据？
LGLJ
2019-10-22 20:47
1楼
| ||||
3248. [POJ 1904]King's Quest
★★★☆ 输入文件：marriage_trouble.in
输出文件：marriage_trouble.out
简单对比时间限制：1 s 内存限制：64 MiB
【题目描述】
本题面由 @数声风笛离亭晚 翻译。
Once upon a time there lived a king and he had $N$ sons. And there were $N$ beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
从前有个国王，他有 $N$ 个儿子。而且王国中有 $N$ 个美丽的姑娘，国王知道他的每个儿子他喜欢哪个姑娘。国王的儿子们年轻，精虫上脑，所以一个儿子有可能喜欢好多个女孩。
因此，国王要求他的巫师为每个儿子找到他喜欢的女孩，以便他们找到真爱。国王的巫师为每个儿子选了一个他可以娶的女孩，这样他就只会喜欢这个女孩，当然，每个漂亮的女孩只需要嫁给国王的其中一个儿子。
然而，国王说：“我喜欢你做的清单，但是我还是有点不满意。对于我的每个儿子，我想知道可以和他结婚的所有女孩。当然了，这前提必须是所有的儿子都要找到一个女孩。”
国王想让巫师解决的问题对他来说太难了。您必须在 2s 内解决此问题来保住巫师的小命(由于国王购置的 $COGS神仙评测机$ 评测速度较快，所以将$时间限制改为 1s $.巫师:"我太难了QAQ")。
【输入格式】
The first line of the input contains $N$ -- the number of king's sons ($1<=N<=2000$). Next $N$ lines for each of king's sons contain the list of the girls he likes: first $Ki$ -- the number of those girls, and then $Ki$ different integer numbers, ranging from $1$ to $N$ denoting the girls. The sum of all $Ki$ does not exceed $200000$.
The last line of the case contains the original list the wizard had made -- $N$ different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
输入的第一行包含一个整数 $ N $，即国王的儿子数。
接下来的 $N$ 行，每一行分别表示：第一个整数 $K$ 表示第 $i$ 个儿子喜欢的女孩数量，然后紧跟着 $K$ 个不同的整数，分别是这些女孩的编号。
最后一行包含巫师列出的原始列表，包含$N$个不同的整数：每个儿子要遵循此列表，他要娶的女孩的编号。清单保证是正确的，也就是说，每个儿子都必须根据清单与所对应的女孩结婚。
【输出格式】
Output $N$ lines.For each king's son first print $Li$ -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print $Li$ different integer numbers denoting those girls, in ascending order.
输出包含$ N $行，每一行的第一个数$ L $表示他喜欢并可以与之结婚的女孩的数量，确保他结婚后，国王的每个儿子都可以结婚。然后紧跟着 $L$ 个整数，即按字典序输出这些女孩的编号。
【样例输入】
4 2 1 2 2 1 2 2 2 3 2 3 4 1 2 3 4
【样例输出】
2 1 2 2 1 2 1 3 1 4
【提示】
This problem has huge input and output data,use $scanf()$ and $printf()$ instead of $cin$ and $cout$ to read data to avoid time limit exceed.
此问题输入和输出数据量较大，请使用$scanf()$和$printf()$代替$cin$和$cout$，避免超时。
对于所有的数据，保证有 $1≤N≤2,000$ ；所有女孩的编号总和不超过 $200,000$。