本文共 2404 字,大约阅读时间需要 8 分钟。
有一个无向图G,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:
1. 对于任意节点连出去的边中,相同颜色的边不超过两条。
2. 图中不存在同色的环,同色的环指相同颜色的边构成的环。
在这个图上,你要支持以下三种操作:
0. 修改一个节点的权值。
1. 修改一条边的颜色。
2. 查询由颜色c的边构成的图中,所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。
第一行包含四个正整数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”。
包含若干行,每行输出一个对应的信息。
1. 对于修改节点权值操作,不需要输出信息。
2. 对于修改边的颜色操作,按以下几类输出:
a) 若不存在连接节点u和节点v的边,输出“No such edge.”。
b) 若修改后不满足条件1,不修改边的颜色,并输出“Error 1.”。
c) 若修改后不满足条件2,不修改边的颜色,并输出“Error 2.”。
d) 其他情况,成功修改边的颜色,并输出“Success.”。
输出满足条件的第一条信息即可,即若同时满足b和c,则只需要输出“Error 1.”。
3. 对于查询操作,直接输出一个整数。 第 5
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
【数据规模】
对于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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!