题解 P2173 【[ZJOI2012]网络】

fdfdf · 2017-12-30 12:10:38 · 题解

关键词:LCT

如果我们把每一种颜色的边所组成的图单独拿出来看的话:

**保证没有同色的环

保证任意节点连出去相同颜色的边不超过两条**

很明显就是几条链吧

再看看我们需要支持的操作:

**改变边的颜色(相当于断一次边,连一次边)

修改权值

查询路径**

很明显就是LCT吧

各位如果不会LCT的请右转>https://www.luogu.org/problemnew/show/P3690

最后看一看数据:

N ≤ 10000,M ≤ 100000,C ≤ 10,K ≤ 100000。

O(NlogNC)直接暴力找颜色就好啦

操作0:

和普通的LCT其实很相似.那么如何同时修改多个LCT呢（⊙ｏ⊙）？

把所有颜色中LCT的位置都转移到LCT->修改->在所有颜色的LCT上update

操作1:

1.对于如何判断u,v两个点是否直接相连,这里推荐另外两种可行的办法:

(1)maktroot(u),access(v),splay(v)

这样如果u,v直接有边相连的话,v(当前splay的根节点)的儿子一定是u且u没有右儿子(就是u,v在splay里中间没有夹其他的点==深度相邻)

(2)一开始存边的时候直接存邻接表,由于每个点连边的总数不超过2*C<=20,常数不大对吧......

2.Error 1:记录连边数组d[c][x]表示点x在颜色c上连边的条数,并判断

3.Error 2:判断是否联通,判断findroot(u)==findroot(v)即可

4.在当前颜色的LCT中删除这条边并且在需求颜色的LCT中添加这条边

5.一个需要注意的地方:新边的颜色有可能和旧边的颜色相等!!!记得加特判!!!

操作2:

模板似的查询...请看代码

就是这样了

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define RG register
using namespace std;
inline int read(){
    RG int data=0,w=1;RG char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
    return data*w;
}
const int N=10010;
const int M=100010;
const int C=10;
int val[N],maxn[C][N],rv[C][N],s[2][C][N],fa[C][N],f[C][N];
int cal[N],top;
int d[C][N];

inline void update(int c,int i){
    maxn[c][i]=max(maxn[c][s[0][c][i]],max(maxn[c][s[1][c][i]],val[i]));
}
inline void pushdown(int c,int i){
    if(!rv[c][i])return;rv[c][i]^=1;rv[c][s[0][c][i]]^=1;rv[c][s[1][c][i]]^=1;swap(s[0][c][i],s[1][c][i]);
}
inline bool isroot(int c,int i){
    return s[0][c][fa[c][i]]!=i&&s[1][c][fa[c][i]]!=i;}

inline bool isr(int c,int i){return s[1][c][fa[c][i]]==i;}
inline void rot(int c,int i){
    RG int j=fa[c][i],k=fa[c][j];
    RG bool b=isr(c,i);
    if(!isroot(c,j))
        s[isr(c,j)][c][k]=i;
    fa[c][i]=k;
    s[b][c][j]=s[!b][c][i];
    if(s[!b][c][i])fa[c][s[!b][c][i]]=j;
    fa[c][j]=i;s[!b][c][i]=j;
    update(c,j);
}

inline void splay(int c,int i){
    cal[++top]=i;
    for(RG int x=i;!isroot(c,x);x=fa[c][x])
        cal[++top]=fa[c][x];
    while(top)pushdown(c,cal[top--]);
    for(RG int j=fa[c][i];!isroot(c,i);rot(c,i),j=fa[c][i])
        if(!isroot(c,j))isr(c,i)^isr(c,j)?rot(c,i):rot(c,j);
    update(c,i);
}

inline void access(int c,int x){for(RG int y=0;x;y=x,x=fa[c][x])splay(c,x),s[1][c][x]=y,update(c,x);}
inline void makeroot(int c,int x){access(c,x);splay(c,x);rv[c][x]^=1;}
inline int findroot(int c,int x){access(c,x);splay(c,x);while(s[0][c][x])x=s[0][c][x];return x;}
inline void split(int c,int x,int y){makeroot(c,x);access(c,y);splay(c,y);}
inline void cut(int c,int x,int y){
    d[c][x]--;d[c][y]--;
    split(c,x,y);fa[c][x]=s[0][c][y]=0;
}
inline void link(int c,int x,int y){
    d[c][x]++;d[c][y]++;
    makeroot(c,x);fa[c][x]=y;
}
//以上,一个正常的LCT
inline void modify_val(int c){//操作1
    RG int x=read(),y=read();
    for(RG int i=0;i<c;i++)access(i,x),splay(i,x);
    val[x]=y;
    for(RG int i=0;i<c;i++)update(i,x);
    return;
}

inline void modify_line(int c){//操作2
    RG int u=read(),v=read(),w=read();
    for(RG int i=0;i<c;i++)
        if(findroot(i,u)==findroot(i,v))
        {
            split(i,u,v);
            if(s[0][i][v]!=u||s[1][i][u])continue;
            if(i==w){//注意此处!!!
                puts("Success.");return;
            }
            if((d[w][u]==2)||(d[w][v]==2)){
                puts("Error 1.");return;
            }
            else if(findroot(w,u)==findroot(w,v)){
                puts("Error 2.");return;
            }
            else{
                cut(i,u,v);link(w,u,v);
                puts("Success.");return;
            }
        }
    puts("No such edge.");
}

inline void query(){//操作3
    RG int c=read(),u=read(),v=read();
    if(findroot(c,u)!=findroot(c,v)){puts("-1");return;}
    split(c,u,v);printf("%d\n",maxn[c][v]);
}

inline void print(int c,int i){
    if(s[0][c][i])print(c,s[0][c][i]);
    printf("(%d:%d)\n",i,c);
    if(s[1][c][i])print(c,s[1][c][i]);
}

int main()
{
    RG int n,m,c,k,u,v,w,opt;
    n=read();m=read();c=read();k=read();
    for(RG int i=1;i<=n;i++)val[i]=read();
    while(m--){
        u=read();v=read();w=read();
        link(w,u,v);
    }
    while(k--){
        opt=read();
        if(!opt)modify_val(c);
        if(opt==1)modify_line(c);
        if(opt==2)query();
    }
    return 0;
}
/*
    食用LCT
    操作0:modify:access->splay->val->update
    操作1:cut所在颜色的边->link修改颜色的边
    找到颜色:暴力O(C) 找不到->No such edge.
    修改:查询度->if(d==2)->Error 1.
    查询联通->if(findroot==findroot)->Error 2.
    成功->Success.
    操作2:query:split->maxn
*/