首页 > 代码库 > ZJOI2012 网络——LCT相关题目
ZJOI2012 网络——LCT相关题目
有一个无向图G，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：
对于任意节点连出去的边中，相同颜色的边不超过两条。
- 图中不存在同色的环，同色的环指相同颜色的边构成的环。
在这个图上，你要支持以下三种操作：
修改一个节点的权值。
修改一条边的颜色。
- 查询由颜色c的边构成的图中，所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。
https://daniu.luogu.org/problem/show?pid=2173
-by luogu
对每个颜色建LCT，对error1数组记录，对error2LCT判联通性，对NO Such...直接写了hash，trie树大概开不下；
发现封装起来非常好；
代码:
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,m,c,p; 5 struct dt{ 6 int fa,ch[2],mark,max,num; 7 }; 8 struct LCT{ 9 dt data[10010]; 10 int tot; 11 void Init(){ 12 data[0].fa=data[0].mark=data[0].max=data[0].max=data[0].num=0; 13 tot=0; 14 } 15 void link(int x,int y){ 16 make_root(x);data[x].fa=y; 17 } 18 void cut(int x,int y){ 19 make_root(x),access(y),splay(y); 20 data[x].fa=data[y].ch[0]=0; 21 up(y); 22 } 23 void access(int x){ 24 int y=0; 25 while(x){ 26 splay(x); 27 data[x].ch[1]=y; 28 up(x); 29 y=x;x=data[x].fa; 30 } 31 } 32 void make_root(int x){ 33 access(x);splay(x);data[x].mark^=1; 34 } 35 int find_root(int x){ 36 access(x);splay(x); 37 while(data[x].ch[0]) 38 x=data[x].ch[0]; 39 return x; 40 } 41 void splay(int x){ 42 push(x); 43 int fa,fafa; 44 for(fa=data[x].fa;data[fa].ch[1]==x||data[fa].ch[0]==x;roll(x),fa=data[x].fa){ 45 fafa=data[fa].fa; 46 if(data[fafa].ch[1]==fa||data[fafa].ch[0]==fa) 47 if((data[fa].ch[0]==x)^(data[fafa].ch[0]==fa)) 48 roll(x); 49 else 50 roll(fa); 51 } 52 } 53 void roll(int now){ 54 int fa=data[now].fa,fafa=data[fa].fa,wh=data[fa].ch[1]==now; 55 data[fa].ch[wh]=data[now].ch[wh^1];data[data[fa].ch[wh]].fa=fa; 56 data[now].ch[wh^1]=fa;data[fa].fa=now; 57 data[now].fa=fafa; 58 if (data[fafa].ch[0]==fa||data[fafa].ch[1]==fa) 59 data[fafa].ch[data[fafa].ch[1]==fa]=now; 60 up(fa);up(now); 61 } 62 void push(int x){ 63 int fa=data[x].fa; 64 if(data[fa].ch[0]==x||data[fa].ch[1]==x) 65 push(fa); 66 down(x); 67 } 68 void up(int x){ 69 int a=data[data[x].ch[0]].max>data[data[x].ch[1]].max?data[data[x].ch[0]].max:data[data[x].ch[1]].max; 70 data[x].max=data[x].num>a?data[x].num:a; 71 } 72 void down(int x){ 73 int i; 74 if(data[x].mark){ 75 i=data[x].ch[0],data[x].ch[0]=data[x].ch[1],data[x].ch[1]=i; 76 data[x].mark=0; 77 data[data[x].ch[0]].mark^=1;data[data[x].ch[1]].mark^=1; 78 } 79 } 80 }; 81 int Hash(int ,int ,int ); 82 LCT lct[10]; 83 int col[10010][10]; 84 int hash[100000]; 85 int poll[200010],next[200010],colway[200010],tot; 86 int main() 87 { 88 int i,j,k,u,v,w; 89 scanf("%d%d%d%d",&n,&m,&c,&p); 90 for(j=0;j<c;j++)lct[j].Init(); 91 for(i=1;i<=n;i++){ 92 scanf("%d",&k); 93 for(j=0;j<c;j++) 94 lct[j].data[i].num=lct[j].data[i].max=k; 95 } 96 for(i=1;i<=m;i++){ 97 scanf("%d%d%d",&u,&v,&w); 98 lct[w].link(u,v); 99 col[u][w]++;col[v][w]++;100 Hash(u*100001+v,1,w),Hash(v*100001+u,1,w);101 }102 for(i=1;i<=p;i++){103 scanf("%d",&j);104 if(j==0){105 scanf("%d%d",&u,&v);106 for(k=0;k<c;k++){107 lct[k].splay(u);108 lct[k].data[u].num=v;109 lct[k].up(u);110 }111 continue;112 }113 if(j==1){114 int lk;115 scanf("%d%d%d",&u,&v,&k);116 lk=Hash(u*100001+v,0,-1);117 if(!lk){118 printf("No such edge.\n");continue;119 }120 if(--lk==k){121 printf("Success.\n");continue;122 }123 if(col[u][k]==2||col[v][k]==2){124 printf("Error 1.\n");continue;125 }126 lct[k].make_root(u);127 if(lct[k].find_root(v)==u){128 printf("Error 2.\n");continue;129 }130 lct[lk].cut(u,v);131 lct[k].link(u,v);132 col[u][lk]--;col[v][lk]--;col[u][k]++;col[v][k]++;133 Hash(u*100001+v,0,k);Hash(v*100001+u,0,k);134 printf("Success.\n");continue;135 }136 if(j==2){137 scanf("%d%d%d",&k,&u,&v);138 lct[k].make_root(u);139 if(lct[k].find_root(v)!=u){140 printf("-1\n");continue;141 }142 lct[k].access(v);143 lct[k].splay(v);144 printf("%d\n",lct[k].data[v].max);145 continue;146 }147 }148 return 0;149 }150 int Hash(int sum,int p,int color){151 int mod=99991,x=sum%mod,i;152 if(!hash[x]){153 if(!p)return 0;154 hash[x]=++tot;155 poll[tot]=sum;colway[tot]=color;156 }157 else{158 i=hash[x];159 while(next[i]&&poll[i]!=sum)160 i=next[i];161 if(p){162 next[i]=++tot;163 poll[tot]=sum;164 colway[tot]=color;165 return 0;166 }167 if(poll[i]!=sum)return 0;168 if(color==-1)return colway[i]+1;169 colway[i]=color;170 }171 return 0;172 }
ZJOI2012 网络——LCT相关题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。