#P18457. Intro: Dawn of a New Era
Intro: Dawn of a New Era
Intro: Dawn of a New Era
题目描述
来自中国各地的朋友们,欢迎来到沈阳!作为出题人,我们和全体工作人员一样,深感荣幸,能够迎接大家参加这场精心准备的赛事,并共同见证东北大学(NEU)连续第九年举办 ICPC 沈阳区域赛。
过去几年对许多人来说都充满挑战。人类社会经历了新冠疫情,我们与之抗争并取得胜利。人类仍然经受着考验,仿佛“暗夜嚎叫者”侵蚀了某些人的心智。我们所在的这所可爱的大学,也刚刚圆满结束百年校庆,翻开了下一个百年的新篇章。这些经历启发了这道开场题的命名。我们衷心希望,每个人都能为梦想不断奋斗,而不甘成为时代的眼泪;也希望大家能用新时代的技术治愈世界,而不是将文明引向落日。
作为东北大学百年校庆的重要组成部分,无人机表演以缤纷色彩点亮夜空,创造出一幅幅令人惊叹的空中画卷。在这道开场题中,你将遇到一个与之有关、看起来仿佛是 NP 困难的问题。

假设无人机表演共有 个场景。每个场景的调色板可以用一个整数集合描述,每个整数标识一种颜色。我们称一个场景调色板中整数值最大的颜色为该场景的 主色。
无人机操作员希望重新安排这些场景的播放顺序。对于重新排序后的每一对相邻场景,如果前一个场景的主色出现在后一个场景的调色板中,就产生一次转场。请构造一个场景排列,使转场总次数尽可能多。
形式化地,令 表示第 个场景的颜色集合,需要构造一个排列 ,使
$$\sum_{i=1}^{n-1}\bigl[\max(S_{p_i})\in S_{p_{i+1}}\bigr]$$在所有长度为 的排列中最大。其中,条件为真时方括号的值为 ,否则为 。
长度为 的排列是由 个整数组成的序列,其中 到 每个整数恰好出现一次。注意:条件要求的是前一个场景的最大色属于下一个集合,仅有任意一种共同颜色并不足以产生转场。
输入格式
第一行包含一个整数 (),表示场景数量。
接下来 行,第 行先包含整数 (),表示第 个调色板的颜色数量;然后给出 个互不相同的整数 (),分别标识其中的颜色。
保证 。颜色 合法,输入中各调色板的颜色无需有序。没有外层测试组数。
输出格式
第一行输出一个整数,表示能取得的最大转场次数。
第二行输出一个长度为 的排列 ,表示场景播放顺序;第 个时段播放场景 。构造必须取得第一行所报告的最大值。若有多个最优排列,输出任意一个即可。
原样例 1
5
3 1 2 4
2 2 3
2 1 3
1 2
2 4 5
3
4 2 3 1 5
原样例 2
3
1 1
1 2
1 3
0
1 2 3
原样例说明
第一个样例中,场景 到场景 、场景 到场景 、场景 到场景 都能产生转场。
第二个样例中,没有两个场景具有共同颜色,因此任意长度为 的排列都可接受。