#P2173. [ZJOI2012] 网络
[ZJOI2012] 网络
题目描述
有一个无向图 ,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:
1、 对于任意节点连出去的边中,相同颜色的边不超过两条。
2、图中不存在同色的环,同色的环指相同颜色的边构成的环。
在这个图上,你要支持以下三种操作:
-
0 x y
表示把节点 的权值改为 -
1 u v w
表示将边 的颜色改为 。 -
2 c u v
表示查询由颜色 的边构成的图中,所有可能在 之间的简单路径上的节点的权值的最大值。
输入格式
第一行四个正整数 ,分别表示节点数、边数、颜色数和操作数。
接下来 行,每行一个正整数 ,为节点 的权值。
之后 行,每行三个正整数 ,为一条连接 节点的边,颜色为。
最后 行,每行若干个正整数,表示一次操作。
输出格式
输出若干行,每行输出一个对应的信息。
1、 对于修改节点权值操作,不需要输出信息。
2、对于修改边的颜色操作,按以下几类输出:
-
若不存在连接节点 和节点 的边,输出
No such edge.
。 -
若修改后不满足条件 ,不修改边的颜色,并输出
Error 1.
。 -
若修改后不满足条件 ,不修改边的颜色,并输出
Error 2.
。 -
其他情况,成功修改边的颜色,并输出
Success.
。
输出满足条件的第一条信息即可,即若同时不满足条件 ,则只需要输出Error 1.
。
3、 对于查询操作,输出一个整数表示答案。若 之间没有颜色 构成的路径,则输出 。
4 5 2 7
1
2
3
4
1 2 0
1 3 1
2 3 0
2 4 1
3 4 0
2 0 1 4
1 1 2 1
1 4 3 1
2 0 1 4
1 2 3 1
0 2 5
2 1 1 4
4
Success.
Error 2.
-1
Error 1.
5
提示
颜色 为实线的边,颜色 为虚线的边,
由颜色 构成的从节点 到节点 的路径有 ,故。
将连接节点 和节点 的边修改为颜色 ,修改成功,输出 Success.
将连接节点 和节点 的边修改为颜色 ,由于修改后会使得存在由颜色 构成的环( ),不满足条件 ,故不修改,并输Error 2
。
不存在颜色 构成的从节点 到节点 的边,输出 -1
。
将连接节点 和节点 的边修改为颜色 ,由于修改后节点 的连出去的颜色为 的边有 条,故不满足条件 ,故不修改,并输出Error 1.
。
将节点 的权值修改为 。
由颜色 构成的从节点 到节点 的路径有 ,故。
【数据范围】
对于 的数据:,,;
另有 的数据:,,,;
对于 的数据:,,,。
,,保证图中没有重边和自环。