问题 28515 -- [ZJOI2012]网络

28515: [ZJOI2012]网络

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

题目描述

有一个无向图G,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:

  1. 对于任意节点连出去的边中,相同颜色的边不超过两条。

  2. 图中不存在同色的环,同色的环指相同颜色的边构成的环。

在这个图上,你要支持以下三种操作:

  1. 修改一个节点的权值。

  2. 修改一条边的颜色。

  3. 查询由颜色c的边构成的图中,所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。

输入输出格式

输入格式:


输入文件network.in的第一行包含四个正整数N, M, C, K,其中N为节点个数,M为边数,C为边的颜色数,K为操作数。

接下来N行,每行一个正整数vi,为节点i的权值。

之后M行,每行三个正整数u, v, w,为一条连接节点u和节点v的边,颜色为w。满足1 ≤ u, v ≤ N,0 ≤ w < C,保证u ≠ v,且任意两个节点之间最多存在一条边(无论颜色)。

最后K行,每行表示一个操作。每行的第一个整数k表示操作类型。

  1. k = 0为修改节点权值操作,之后两个正整数x和y,表示将节点x的权值vx修改为y。

  2. k = 1为修改边的颜色操作,之后三个正整数u, v和w,表示将连接节点u和节点v的边的颜色修改为颜色w。满足0 ≤ w < C。

  3. k = 2为查询操作,之后三个正整数c, u和v,表示查询所有可能在节点u到节点v之间的由颜色c构成的简单路径上的节点的权值的最大值。如果不存在u和v之间不存在由颜色c构成的路径,那么输出“-1”。


输出格式:


输出文件network.out包含若干行,每行输出一个对应的信息。

  1. 对于修改节点权值操作,不需要输出信息。

  2. 对于修改边的颜色操作,按以下几类输出:

a) 若不存在连接节点u和节点v的边,输出“No such edge.”。

b) 若修改后不满足条件1,不修改边的颜色,并输出“Error 1.”。

c) 若修改后不满足条件2,不修改边的颜色,并输出“Error 2.”。

d) 其他情况,成功修改边的颜色,并输出“Success.”。

输出满足条件的第一条信息即可,即若同时满足b和c,则只需要输出“Error 1.”。

  1. 对于查询操作,直接输出一个整数。


输入输出样例

输入样例#1: 复制
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
输出样例#1: 复制
4
Success.
Error 2.
-1
Error 1.
5

说明

颜色0为实线的边,颜色1为虚线的边,

由颜色0构成的从节点1到节点4的路径有1 – 2 – 4,故max{v1, v2, v4} = max{ 1, 2, 4 } = 4。

将连接节点1和节点2的边修改为颜色1,修改成功,输出“Success.”

将连接节点4和节点3的边修改为颜色1,由于修改后会使得存在由颜色1构成的环( 1 – 2 – 4 – 3 – 1 ),不满足条件2,故不修改,并输出“Error 2”。

不存在颜色0构成的从节点1到节点4的边,输出“-1”。

将连接节点2和节点3的边修改为颜色1,由于修改后节点2的连出去的颜色为1的边有3条,故不满足条件1,故不修改,并输出“Error 1.”。

将节点2的权值修改为5。

由颜色1构成的从节点1到节点4的路径有 1 – 2 – 4,故max{v1, v2, v4} = max{ 1, 5, 4 } = 5。

【数据规模】

对于30%的数据:N ≤ 1000,M ≤ 10000,C ≤ 10,K ≤ 1000。

另有20%的数据:N ≤ 10000,M ≤ 100000,C = 1,K ≤ 100000。

对于100%的数据:N ≤ 10000,M ≤ 100000,C ≤ 10,K ≤ 100000。

输入

输出

提示

来源

[提交][状态]