【bzoj2816】【ZJOI2012】【网络】【lct】
发布日期:2021-11-16 15:38:21 浏览次数:5 分类:技术文章

本文共 2404 字,大约阅读时间需要 8 分钟。

题目描述 Description

有一个无向图G,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:
1. 对于任意节点连出去的边中,相同颜色的边不超过两条。
2. 图中不存在同色的环,同色的环指相同颜色的边构成的环。
在这个图上,你要支持以下三种操作:
0. 修改一个节点的权值。
1. 修改一条边的颜色。
2. 查询由颜色c的边构成的图中,所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。

输入描述 Input Description

第一行包含四个正整数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表示操作类型。
0. k = 0为修改节点权值操作,之后两个正整数x和y,表示将节点x的权值vx修改为y。
1. k = 1为修改边的颜色操作,之后三个正整数u, v和w,表示将连接节点u和节点v的边的颜色修改为颜色w。满足0 ≤ w < C。
2. k = 2为查询操作,之后三个正整数c, u和v,表示查询所有可能在节点u到节点v之间的由颜色c构成的简单路径上的节点的权值的最大值。如果不存在u和v之间不存在由颜色c构成的路径,那么输出“-1”。

输出描述 Output Description

包含若干行,每行输出一个对应的信息。
1. 对于修改节点权值操作,不需要输出信息。
2. 对于修改边的颜色操作,按以下几类输出:
a) 若不存在连接节点u和节点v的边,输出“No such edge.”。
b) 若修改后不满足条件1,不修改边的颜色,并输出“Error 1.”。
c) 若修改后不满足条件2,不修改边的颜色,并输出“Error 2.”。
d) 其他情况,成功修改边的颜色,并输出“Success.”。
输出满足条件的第一条信息即可,即若同时满足b和c,则只需要输出“Error 1.”。
3. 对于查询操作,直接输出一个整数。 第 5

样例输入 Sample Input

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

样例输出 Sample Output

4
Success.
Error 2.
-1
Error 1.
5

数据范围及提示 Data Size & Hint

【数据规模】
对于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。

题解:因为c比较小,所以建c棵lct即可,注意修改权值的时候需要在所有的lct中修改。

代码:

#include
#include
#include
#include
#define N 10010using namespace std;int x,y,c[15][N][2],fa[15][N],rev[15][N],n,k,kind,T,cz,v[N],p[15][N],mx[15][N];int st[N],q[N],m;struct use{int st,en,c;}e[N*10*2];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}bool cmp(use a,use b){return a.st
>1; if (e[mid].st
e[i].en) swap(e[i].st,e[i].en); link(e[i].c,e[i].st,e[i].en); } sort(e+1,e+m+1,cmp); for (int i=1;i<=T;i++){ kind=read();x=read();y=read(); if (kind==0){ for (int j=0;j
y) swap(x,y);int t=fd(x,y); if (k!=e[t].c){ if (e[t].st!=x||e[t].en!=y){puts("No such edge.");continue;} if (p[k][x]>=2||p[k][y]>=2){puts("Error 1.");continue;} if (find(k,x)==find(k,y)){puts("Error 2.");continue;} cut(e[t].c,x,y);link(k,x,y);e[t].c=k; } puts("Success."); } if (kind==2){ k=read(); if(find(x,y)!=find(x,k)) printf("-1\n"); else{split(x,y,k);printf("%d\n",v[mx[x][y]]);} } }}

转载地址:https://blog.csdn.net/sunshinezff/article/details/50987810 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj4043】【Cerc2014】【Vocabulary】【dp+预处理】
下一篇:【bzoj4025】【二分图】【lct】

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月23日 18时47分46秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21
.net core linux 桌面应用,C# dotnet core + AvaloniaUI 开发桌面软件,hello world 2019-04-21
linux tcp 113错误,linux系统报tcp_mark_head_lost错误的处理方法 2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式... 2019-04-21
python学画画_python学画画(下) 2019-04-21
云栖社区 mysql_【直播结束,已更新回放】PG、MySQL到底哪个好?云栖说这次请来五位专家撕了一下-阿里云开发者社区... 2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福 2019-04-21
mysql驱动多次执行问题_Laravel5.2队列驱动expire参数设置带来的重复执行问题 数据库驱动... 2019-04-21
mysql获取刚新增的数据库_如何取得刚插入数据库的数据的id mysql 2019-04-21
python将10到1递减_(Python)如何将3个递减列表合并成一个递减列表? 2019-04-21
python脚本怎么用来处理数据_长时间运行数据处理python脚本的程序结构 2019-04-21
python转成c 语言_将Python对象转换为C void类型 2019-04-21
resin mysql_Eclipse+resin+mysql 安装及环境配置 2019-04-21