问题 25249 --会议(meeting)

25249: 会议(meeting)

时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 25
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

      小姜摆逆天之阵救人最终功亏一篑,虽然救出了魔君父亲,但雨柔永远的离他而去。被救的魔君姜世离却丝毫没有动摇他吞并人魔两界的野心,他很快回到魔教大营,准备组织人马进攻蜀山夺取伏羲剑并复当年被封印之仇。但是由于魔教多年无人经营,各个护法和诸部众都分布在不同的地区,姜世离准备集结他们来计划进攻方案。

       人界各地都已被蜀山布上伏魔法阵,这些法阵由一些魔法点组成,某两个魔法点之间有结界相连,不同结界不会相交,任意两个魔法点之间最多只有一道结界,人界的任意两个地区都可以通过一道或多道结界联通,这样,整个人界就被这些结界分成许多块地区。由于某些原因,现在魔界各精英在不同的魔法点处,但是每个魔法点最多有一个魔族。为了避免被蜀山发现而计划败露,姜世离把集结地点会定在某一个地区内,在前往集结地的过程中,魔族们不能经过魔法点,另一方面,他们通过结界也很麻烦,所以他们想经过最少的结界,为此,姜世离决定选择一个地区作为集结地,使所有魔族到达该地区需要穿过的结界数最少。

      假设一共有N 个魔法点,他们分别用1 到N 的整数来编号,在图1 中,各魔法点被表示为相应编号的顶点,而结界则被表示为连接顶点的直线段,假设共有三名魔教精英,分别在魔法点3,6 和9,那么最优的集结地区和各魔族的路线如图2 所示,按照这种方案,魔族们共要穿过2 道结界,魔法点9 的魔族要穿过魔法点2 和4 之间的结界,而魔法点6 的魔族则要穿过魔法点4 和7 之间的结界。
       魔君姜世离已经急于进攻而不屑于规划集结地点了,于是他想到了地牢中的你,他给了你魔法点,地区,魔族属地和结界情况等信息,让你求出最优集结点,并让你给出相应的所有成员需要穿过的结界总数,还答应如果你在一秒钟内解决问题就放了你,否则~~,你决定赶快解决问题,好在魔教进攻之前通知蜀山。

输入

第一行是一个正整数M,表示地区个数。
第二行也是一个正整数N,表示魔法点的个数。
第三行还是一个正整数L,表示魔教精英人数。
第四行是L 个互异的整数,对应各个精英的所在魔法点编号,他们按升序排列。
接下来2M 行,两两成对,分别描述各个地区,前两行对应第一个地区,接下来
两行对应第二个地区,以此类推。
每两行中的前一行是一个整数I,I 是沿对应地区边界的城市数目,沿该地区边
界环行一周,将依次经过这I 个魔法点,后一行中给出了I 个整数,记录了按顺
时针方向环行依次所访问的魔法点编号。
最后两行对应的那个地区与众不同,它包围了所有的其他地区和所有的魔法点,
注意:这各地区边界上的魔法点编号,按照逆时针的环行方向依次给出。

输出

第一行一个整数,表示你找的所有成员需要穿过的结界总数的最小值。
第二行也是一个整数,表示可以进行集结的地区编号,存在多个时输出编号最小的即可。

样例输入

10
10
3
3 6 9
3
1 2 3
3
1 3 7
4
2 4 7 3
3
4 6 7
3
4 8 6
3
6 8 7
3
4 5 8
4
7 8 10 9
3
5 10 8
7
7 9 10 5 4 2 1

样例输出

2
3

提示

【样例解释】

样例即对应题目中描述的例子。

【数据范围】

2≤M≤200

3≤N≤250

1≤L≤30

如果你看到这里,请用Adobe Acrobat X Pro 打开本题目。

来源

[提交][状态]