当前位置：网站首页>bzoj2816 [ZJOI2012]网络

bzoj2816 [ZJOI2012]网络

2022-08-08 14:57:00 【51CTO】


​ ​http://www.elijahqi.win/2018/03/08/bzoj2816/​​​ ‎
题目描述

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

对于任意节点连出去的边中，相同颜色的边不超过两条。
图中不存在同色的环，同色的环指相同颜色的边构成的环。
在这个图上，你要支持以下三种操作：

修改一个节点的权值。
修改一条边的颜色。
查询由颜色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表示操作类型。

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

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

对于修改节点权值操作，不需要输出信息。
对于修改边的颜色操作，按以下几类输出：
a) 若不存在连接节点u和节点v的边，输出“No such edge.”。

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

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

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

输出满足条件的第一条信息即可，即若同时满足b和c，则只需要输出“Error 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。

每个点拆成c个颜色看 相当于一个森林 然后进行lct基础操作即可 注意判断这个是说 是否两点间一种颜色的边也不存在 而不是是否存在当前这种颜色的边 还有判断是否处于链的两端记录In数组即可 一开始我naive了 只有20分

      
      

       
       #include<map>
       
       
#include<queue>
       
       
#include<cstdio>
       
       
#include<algorithm>
       
       
#define N 110000
       
       
#define pa pair<int,int>
       
       
using namespace std;
       
       
inline char gc(){
       
       
    static char now[1<<16],*S,*T;
       
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
       
    return *S++;
       
       
}
       
       
inline int read(){
       
       
    int x=0,f=1;char ch=gc();
       
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
       
    return x*f;
       
       
}
       
       
int mx[N],size[N],c[N][2],q[N],top,n,m,C,k,v[N],fa[N],in[N];
       
       
bool rev[N];map<pa,int> mm;
       
       
inline void update(int x){
       
       
    mx[x]=max(v[x],max(mx[c[x][0]],mx[c[x][1]]));
       
       
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
       
       
}
       
       
inline void pushdown(int x){
       
       
    if (!rev[x]) return;
       
       
    int l=c[x][0],r=c[x][1];
       
       
    swap(c[x][0],c[x][1]);rev[l]^=1;
       
       
    rev[r]^=1;rev[x]=0;
       
       
}
       
       
inline bool isroot(int x){
       
       
    return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
       
       
}
       
       
inline void rotate(int x){
       
       
    int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
       
       
    if (!isroot(y)) c[z][c[z][1]==y]=x;
       
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
       
}
       
       
inline void splay(int x){
       
       
    q[top=1]=x;for (int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
       
       
    while(top) pushdown(q[top--]);
       
       
    while(!isroot(x)){
       
       
        int y=fa[x],z=fa[y];
       
       
        if (!isroot(y)) {
       
       
            if (c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);
       
       
        }rotate(x);
       
       
    }
       
       
}
       
       
inline void access(int x){
       
       
    for (int t=0;x;t=x,x=fa[x]) splay(x),c[x][1]=t,update(x);
       
       
}
       
       
inline void makeroot(int x){
       
       
    access(x);splay(x);rev[x]^=1;
       
       
}
       
       
inline int find(int x){
       
       
    access(x);splay(x);while(c[x][0]) x=c[x][0];return x;
       
       
}
       
       
inline bool check(int x,int y){
       
       
    if(find(x)!=find(y)) return 0;
       
       
    makeroot(x);access(y);splay(y);
       
       
    if(c[y][0]!=x) return 0;if (c[x][1]) return 0;
       
       
    return 1;
       
       
}
       
       
inline bool check1(int x,int y){
       
       
    return (in[x]<2)&&(in[y]<2);
       
       
}
       
       
inline bool check2(int x,int y){
       
       
    return find(x)!=find(y);
       
       
}
       
       
inline void cut(int x,int y){
       
       
    --in[x];--in[y];makeroot(x);access(y);splay(y);c[y][0]=fa[c[y][0]]=0;update(y);
       
       
}
       
       
inline void link(int x,int y){
       
       
    makeroot(x);fa[x]=y;++in[x];++in[y];
       
       
}
       
       
int main(){
       
       
    freopen("bzoj2816.in","r",stdin);
       
       
    freopen("bzoj2816.out","w",stdout);
       
       
    n=read();m=read();C=read();k=read();
       
       
    for (int i=1;i<=n;++i){
       
       
        int a=read();
       
       
        for (int j=0;j<C;++j) mx[j*n+i]=v[j*n+i]=a;
       
       
    }
       
       
    for (int i=1;i<=m;++i){
       
       
        int x=read(),y=read(),cc=read(); 
       
       
        mm[make_pair(x,y)]=cc;mm[make_pair(y,x)]=cc;
       
       
        link(cc*n+x,cc*n+y);
       
       
    }
       
       
    while(k--){
       
       
        int op=read();if (op==0){int x=read(),y=read();
       
       
            for (int i=0;i<C;++i) {
       
       
                int xx=i*n+x;splay(xx);v[xx]=y;update(xx);
       
       
            }
       
       
        }
       
       
        if (op==1){
       
       
            int x=read(),y=read(),w=read();int lc=mm[make_pair(x,y)];int flag=-1;
       
       
            for (int i=0;i<C;++i) if (check(i*n+x,i*n+y)) {flag=i;break;}
       
       
            if (flag==w) {puts("Success.");continue;}
       
       
            if (flag==-1) {puts("No such edge.");continue;}
       
       
            if (!check1(w*n+x,w*n+y)) {puts("Error 1.");continue;}
       
       
            if (!check2(w*n+x,w*n+y)) {puts("Error 2.");continue;}puts("Success.");
       
       
            cut(lc*n+x,lc*n+y);link(w*n+x,w*n+y);mm[make_pair(x,y)]=mm[make_pair(y,x)]=w;
       
       
        }
       
       
        if (op==2){
       
       
            int w=read(),x=read(),y=read();x=w*n+x;y=w*n+y;
       
       
            if (find(x)!=find(y)) {puts("-1");continue;}
       
       
            makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);
       
       
        }
       
       
    }
       
       
    return 0;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    • 
       
       
  • 51.
    • 
       
       
  • 52.
    • 
       
       
  • 53.
    • 
       
       
  • 54.
    • 
       
       
  • 55.
    • 
       
       
  • 56.
    • 
       
       
  • 57.
    • 
       
       
  • 58.
    • 
       
       
  • 59.
    • 
       
       
  • 60.
    • 
       
       
  • 61.
    • 
       
       
  • 62.
    • 
       
       
  • 63.
    • 
       
       
  • 64.
    • 
       
       
  • 65.
    • 
       
       
  • 66.
    • 
       
       
  • 67.
    • 
       
       
  • 68.
    • 
       
       
  • 69.
    • 
       
       
  • 70.
    • 
       
       
  • 71.
    • 
       
       
  • 72.
    • 
       
       
  • 73.
    • 
       
       
  • 74.
    • 
       
       
  • 75.
    • 
       
       
  • 76.
    • 
       
       
  • 77.
    • 
       
       
  • 78.
    • 
       
       
  • 79.
    • 
       
       
  • 80.
    • 
       
       
  • 81.
    • 
       
       
  • 82.
    • 
       
       
  • 83.
    • 
       
       
  • 84.
    • 
       
       
  • 85.
    • 
       
       
  • 86.
    • 
       
       
  • 87.
    • 
       
       
  • 88.
    • 
       
       
  • 89.
    • 
       
       
  • 90.
    • 
       
       
  • 91.
    • 
       
       
  • 92.
    • 
       
       
  • 93.
    • 
       
       
  • 94.
    • 
       
       
  • 95.
    • 
       
       
  • 96.
    • 
       
       
  • 97.
    • 
       
       
  • 98.
    • 
       
       
  • 99.
    • 
       
       
  • 100.
    • 
       
       
  • 101.
    • 
       
       
  • 102.
    • 
       
       
  • 103.
    • 
       
       
  • 104.
    • 
       
       
  • 105.
    • 
       
       
  • 106.
    • 
       
       
  • 107.
    • 
       
       
  • 108.
    • 
       
       
  • 109.
    • 
       
       
  • 110.
    • 
       
       
  • 111.
    • 
       
       
  • 112.
    •


原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5555926

边栏推荐

猜你喜欢

随机推荐