[ZJOI2012][bzoj 2816] 网络 network [LCT]

 ?1 /************************************************************** ?2 ????Problem: 2816 ?3 ????User: dedicatus545 ?4 ????Language: C++ ?5 ????Result: Accepted ?6 ????Time:8032 ms ?7 ????Memory:6688 kb ?8 ****************************************************************/ ?9 ??10 #include<iostream> 11 #include<cstdio> 12 #include<algorithm> 13 #include<cstring> 14 #include<unistd.h> 15 #define col(i,c) n*c+i 16 using namespace std; 17 inline int read(){ 18 ????int re=0,flag=1;char ch=getchar(); 19 ????while(ch>‘9‘||ch<‘0‘){ 20 ????????if(ch==‘-‘) flag=-1; 21 ????????ch=getchar(); 22 ????} 23 ????while(ch>=‘0‘&&ch<=‘9‘) re=(re<<1)+(re<<3)+ch-‘0‘,ch=getchar(); 24 ????return re*flag; 25 } 26 struct edge{ 27 ????int to,next,w; 28 }e[200010]; 29 int n,m,C,cnt=-1,q,first[100010],color[10010][11]; 30 int fa[100010]={0},ch[100010][2]={0},w[100010],a[100010]; 31 bool rev[100010]={0},rt[100010]={0}; 32 void _swap(int &l,int &r){l^=r;r^=l;l^=r;} 33 void update(int x){a[x]=max(a[ch[x][0]],max(a[ch[x][1]],w[x]));}; 34 void pushrev(int x){ 35 ????if(!x) return; 36 ????_swap(ch[x][0],ch[x][1]); 37 ????rev[x]^=1; 38 } 39 void pushdown(int x){ 40 ????if(!x) return; 41 ????if(rev[x]){ 42 ????????pushrev(ch[x][0]); 43 ????????pushrev(ch[x][1]); 44 ????????rev[x]=0; 45 ????} 46 } 47 void push(int x){ 48 ????//cout<<"push "<<x<<‘ ‘<<rt[x]<<‘\n‘; 49 ????if(!x) sleep(1000); 50 ????if(!rt[x]) push(fa[x]); 51 ????pushdown(x); 52 } 53 int get(int x){return ch[fa[x]][1]==x;} 54 void rotate(int x){ 55 ????//cout<<"rotate "<<x<<‘\n‘; 56 ????int f=fa[x],ff=fa[f],son=get(x); 57 ????ch[f][son]=ch[x][son^1]; 58 ????if(ch[f][son]) fa[ch[f][son]]=f; 59 ????ch[x][son^1]=f;fa[f]=x; 60 ????fa[x]=ff; 61 ????if(rt[f]) rt[x]=1,rt[f]=0; 62 ????else ch[ff][ch[ff][1]==f]=x; 63 ????update(f);update(x); 64 } 65 void splay(int x){ 66 ????//cout<<"splay "<<x<<‘\n‘; 67 ????push(x); 68 ????for(int f;!rt[x];rotate(x)) 69 ????????if(!rt[f=fa[x]]) 70 ????????????rotate((get(x)==get(f))?f:x); 71 ????update(x); 72 } 73 void access(int x){ 74 ????//cout<<"access "<<x<<‘\n‘; 75 ????int y=0; 76 ????do{ 77 ????????splay(x); 78 ????????rt[ch[x][1]]=1; 79 ????????rt[ch[x][1]=y]=0; 80 ????????x=fa[y=x]; 81 ????????update(x); 82 ????}while(x); 83 } 84 void makeroot(int x){ 85 ????//cout<<"makeroot "<<x<<‘\n‘; 86 ????access(x);splay(x);pushrev(x); 87 } 88 bool judge(int x,int y){ 89 ????while(fa[x]) x=fa[x]; 90 ????while(fa[y]) y=fa[y]; 91 ????return x==y; 92 } 93 void init(int x,int y){ 94 ????//cout<<"init "<<x<<‘ ‘<<y<<‘\n‘; 95 ????makeroot(x);fa[x]=y; 96 } 97 int link(int x,int y){ 98 ????if(judge(x,y)) return 0; ?99 ????makeroot(x);fa[x]=y;100 ????return 1;101 }102 int cut(int x,int y){103 ????if(!judge(x,y)) return 0;104 ????makeroot(x);splay(y);105 ????fa[ch[y][0]]=fa[y];106 ????rt[ch[y][0]]=1;107 ????fa[y]=0;ch[y][0]=0;108 ????return 1;109 }110 void add(int u,int v,int w){111 ????e[++cnt]=(edge){v,first[u],w};first[u]=cnt;112 ????e[++cnt]=(edge){u,first[v],w};first[v]=cnt;113 }114 int split(int u,int v){115 ????if(!judge(u,v)) return -1;116 ????makeroot(u);access(v);splay(v);117 ????return a[v];118 }119 int main(){120 ???// freopen("networkzj.in","r",stdin);121 ??// ?freopen("networkzj.out","w",stdout);122 ????memset(first,-1,sizeof(first));123 ????int i,j,t1,t2,t3,t4;124 ????n=read();m=read();C=read();q=read();125 ????for(i=1;i<=n;i++){126 ????????t1=read();127 ????????for(j=0;j<C;j++) a[col(i,j)]=w[col(i,j)]=t1,rt[col(i,j)]=1;128 ????}129 ????130 ????for(i=1;i<=m;i++){131 ????????t1=read();t2=read();t3=read();132 ????????init(col(t1,t3),col(t2,t3));133 ????????add(t1,t2,t3);134 ????????color[t1][t3]++;color[t2][t3]++;135 ????}136 ????//for(i=1;i<=n;i++){137 ????????//for(j=0;j<C;j++) cout<<color[i][j]<<‘ ‘;138 ????????//cout<<‘\n‘;139 ????//}140 ????for(i=1;i<=q;i++){141 ????????//cout<<"operation "<<i<<‘\n‘;142 ????????t1=read();143 ????????if(t1==0){144 ????????????t2=read();t3=read();145 ????????????for(j=0;j<C;j++){146 ????????????????makeroot(col(t2,j));w[col(t2,j)]=t3;update(col(t2,j));147 ????????????}148 ????????}149 ????????if(t1==1){150 ????????????t2=read();t3=read();t4=read();bool flag=1,f=1;151 ????????????for(j=first[t2];~j;j=e[j].next) 152 ????????????????if(e[j].to==t3){153 ????????????????????flag=0;154 ????????????????????if(e[j].w==t4) f=0;155 ????????????????}156 ????????????if(flag){157 ????????????????printf("No such edge.\n");158 ????????????????continue;159 ????????????} 160 ????????????if(f&&(color[t2][t4]==2||color[t3][t4]==2)){161 ????????????????printf("Error 1.\n");continue;162 ????????????}163 ????????????if(f&&(judge(col(t2,t4),col(t3,t4)))){164 ????????????????printf("Error 2.\n");continue;165 ????????????}166 ????????????for(j=first[t2];~j;j=e[j].next){167 ????????????????if(e[j].to==t3){168 ????????????????????color[t2][e[j].w]--;color[t3][e[j].w]--;169 ????????????????????cut(col(t2,e[j].w),col(t3,e[j].w));170 ????????????????????e[j].w=e[j^1].w=t4;171 ????????????????????color[t2][t4]++;color[t3][t4]++;172 ????????????????????link(col(t2,t4),col(t3,t4));173 ????????????????????printf("Success.\n");break;174 ????????????????} 175 ????????????}176 ????????}177 ????????if(t1==2){178 ????????????t2=read();t3=read();t4=read();179 ????????????printf("%d\n",split(col(t3,t2),col(t4,t2)));180 ????????}181 ????}182 }