P2173 [ZJOI2012]网络

    • 340通过
    • 1K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT Splay 各省省选 2012 浙江 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一个无向图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。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。