/ OIer TK / 题库 /

小珍的路径

小珍的路径

测试数据来自 system/1457

描述

新的学年开始了,经过期末考的惨败,小珍在这个学期用功多了,自然也多出许多空闲的时间来。于是yuhc给她出了一道难题。

yuhc给她一个含n个结点,m条边的图。图中每两结点间的连线(路径长度)很长,小珍从一个结点寻找到另一个结点需要一定的时间,称为顺线时间。如果在yuhc给定的时间t内小珍能够从结点1出发经过x[1],x[2],……搜寻到x[k],则称1,x[1],x[2],……,x[k]是一条合法路径。每个结点都含有一个不大于25的非负权值,每个权值看作字符串中的一位,比如字符串”7,8,9,10,1”与字符串”7,8,10,9,5”相比前者更大(逗号为字符串每位的分隔符)。现在小珍要从结点1出发,寻找一条Z路径,所谓Z路径,是指满足下面三点要求的路径:
1.路径上共有偶数个结点(包括结点1)
2.它是最长的一条偶数结点数的路径
3.同等长度的路径中,它的权值按搜索顺序组成的字符串,其字典序最小。

以上的长度是指结点数-1。

yuhc要求小珍给出图中最长的合法路径的长度,以及Z路径的权值序列。并对Z路径的权值序列作以下处理:
1.将求得的权值序列的首尾相接,形成一个环链。
2.每次将相邻的两数同时加上一个小于等于200的正整数。

那么经过有限次的第二步操作,能否使环链上所有的数字相同呢?如果能够达到,则称这个Z路径具有可加性。小珍要做的,是判断Z路径是否具有可加性,如果有,则回答”YES”,否则,回答”NO”。

由于yuhc比较空,所以他画了一个很大很大的图,因此小珍的工作量很大,自然需要你的帮忙。

数据中保证存在偶数结点的合法路径。任意一个结点只能在一条路径中出现一次。

下面的图给出了一个实例。图中,n=12,m=11,t=12。

图片
最长合法路径为1-8-9-10-11(数字为结点序号),所以最长路径长度为5。

最长偶结点路径有两条:
1-2-3-4,对应的结点权值为10-5-2-12;
1-2-3-5,对应的结点权值为10-5-2-7;
由于10-5-2-7字典序小于10-5-2-12,所以1-2-3-5为Z路径。它的权值序列为10 5 2 7。

然后将权值序列绕成一个环链,环链及操作如下图:
图片
所以该Z路径具有可加性。

格式

输入格式

输入包含m+2行:
第1行,用空格隔开的3个正整数,依次表示n,m,t。

第2行,共n个数,第i个数表示序号为i的结点的权值,权值为不大于25的非负整数。

第3行到第m+2行,每行给出3个用空格隔开的正整数,依次表示每一条边的两个端点的编号及它们之间的顺线时间。

对于所有数据,n<=20,t<=1E5。

输出格式

输出包含3行:
第1行为图中最长的合法路径的长度。

第2行为Z路径的结点的权值,按搜索顺序输出,之间用一个空格隔开。

第3行为环链可加性判定结果,输出YES或NO。

样例1

样例输入1

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

样例输出1

5
10 5 2 7
YES

限制

所有数据时限为1s

提示

1.环链处理时不要进行取模。

2.为了简化题目:不必输出环链处理步骤和最终环链上的数字。

3.图中所有的边都是单向的。

4.数据保证仅存在一条Z路径。

来源

jszx

信息

ID
1428
难度
(无)
分类
搜索 | 其他 | 数学 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者