【题解】BZOJ 2816 [ZJOI2012]网络

请注意,本文编写于 256 天前,最后修改于 256 天前,其中某些信息可能已经过时。

Probelm

传送门 >ω<

题目大意:
一个无向图中的边有多种颜色,一个节点连出去同色边不超过两条,不存在同色环,需要支持三种操作

  1. 修改单点权值
  2. 修改一条边颜色
  3. 查询某种颜色边组成的图中 $u$ , $v$ 路径权值最大值

Solution

此题相当于给定几个森林,要求支持删边,加边,求路径最大值
考虑到颜色不多,我们可以用多个 LCT 维护森林连通性问题

每个 LCT 单独维护一种颜色
修改修改某条边颜色时只需要寻找在某个 LCT 中是否这两个点相邻
只需要将两者放到同一 Splay 中看是否深度间隔为 $1$ 即可判断

剩下的就是基本操作了~

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
#define L ch[x][0]
#define R ch[x][1]
int val[N];
struct LCT {
    int ch[N][2] , f[N] , rev[N] , max_val[N];
    int sta[N];
    bool get(int x) {return ch[f[x]][1] == x;}
    void pushdown(int x) {if(rev[x]) {rev[x] ^= 1; rev[L] ^= 1; rev[R] ^= 1; swap(L , R);}}
    bool isroot(int x) {return ch[f[x]][0] != x && ch[f[x]][1] != x;}
    void update(int x) {max_val[x] = max(max(max_val[L] , max_val[R]) , val[x]);}
    void rotate(int x) {
        int old = f[x] , oldf = f[old] , w = get(x);
        if(!isroot(old)) ch[oldf][ch[oldf][1] == old] = x;
        ch[old][w] = ch[x][w ^ 1]; f[ch[old][w]] = old;
        ch[x][w ^ 1] = old; f[old] = x;
        f[x] = oldf;
        update(old); update(x);
    }
    void splay(int x) {
        int fa = x , top = 0;
        sta[++ top] = fa;
        while(!isroot(fa)) {sta[++top] = fa = f[fa];}
        while(top) pushdown(sta[top --]);
        for(int fa ; !isroot(x) ; rotate(x)) {
            if(!isroot(fa = f[x]))
                rotate(get(x) == get(fa) ? fa : x);
        }
    }
    void access(int x) {
        for(int i = 0 ; x ; i = x , x = f[x]) {
            splay(x);
            R = i;
            update(x);
        }
    }
    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }
    int find(int x) {
        access(x);
        splay(x);
        while(L) x = L;
        return x;
    }
    void split(int x , int y) {
        makeroot(x);
        access(y);
        splay(y);
    }
    bool connect(int x , int y) {
        split(x , y);
        return ch[x][1] == 0 && ch[y][0] == x;
    }
    void cut(int x , int y) {
        if(connect(x , y)) {
            ch[y][0] = 0;
            f[x] = 0;
        }
    }
    void link(int x , int y) {
        makeroot(x);
        f[x] = y;
    }
}lct[10];
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
    while(ch >= '0' &&ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int num[N][10];
int main() {
    int n = read() , m = read() , c = read() , k = read();
    for(int i = 1 ; i <= n ; ++ i) {
        val[i] = read();
        for(int j = 0 ; j < c ; ++ j) lct[j].update(i);
    }
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read() , w = read();
        lct[w].link(u , v);
        ++ num[u][w]; ++ num[v][w];
    }
    for(int i = 1 ; i <= k ; ++ i) {
        int opt = read();
        switch(opt) {
            case 0 : {
                int x = read() , y = read();
                for(int j = 0 ; j < c ; ++ j) {
                    lct[j].access(x); lct[j].splay(x);
                }
                val[x] = y;
                for(int j = 0 ; j < c ; ++ j)
                    lct[j].update(x);
                break;
            }
            case 1 : {
                int u = read() , v = read() , w = read() , flag = 1;
                for(int j = 0 ; j < c ; ++ j)
                    if(lct[j].connect(u , v)) {
                        if(j == w) {puts("Success.");}
                        else if(num[u][w] >= 2 || num[v][w] >= 2) puts("Error 1.");
                        else if(lct[w].find(u) == lct[w].find(v)) puts("Error 2.");
                        else {
                            lct[j].cut(u , v);
                            lct[w].link(u , v);
                            -- num[u][j]; -- num[v][j];
                            ++ num[u][w]; ++ num[v][w];
                            puts("Success.");
                        }
                        flag = 0;
                        break;
                    }
                if(flag) puts("No such edge.");
                break;
            }
            case 2 : {
                int w = read() , u = read() , v = read() , fx = lct[w].find(u) , fy = lct[w].find(v);
                if(fx != fy) puts("-1");
                else {
                    lct[w].split(u , v);
                    printf("%d\n" , lct[w].max_val[v]);
                }
                break;
            }
        }
    }
    return 0;
}
Comments

添加新评论