【BZOJ4736】温暖会指引我们前行（LCT）
2024-10-21 09:27:52
题意：有一张图，每条边有一个不同的编号，长度和权值，维护以下操作：
1.加边
2.修改边长
3.询问两点之间在最小权值最大的前提下的唯一路径长度
n<=100000 m<=300000
思路：RYZ作业
BZOJ上有四组数据的输入不完整，输出没问题
LCT维护最大生成树，维护子树和，和子树中权值最小的位置即可
var t:array[..,..]of longint;
sum:array[..]of int64;
f:array[..,..]of longint;
w,l1,mx,fa,q,rev:array[..]of longint;
n,m,x,y,top,tot,id,i,len,s,ll,tt,j,tmp,now:longint;
ch:string; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; function isroot(x:longint):boolean;
begin
if (t[fa[x],]<>x)and(t[fa[x],]<>x) then exit(true);
exit(false);
end; procedure pushup(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
sum[x]:=sum[l]+sum[r]+l1[x];
mx[x]:=x;
if w[mx[l]]<w[mx[x]] then mx[x]:=mx[l];
if w[mx[r]]<w[mx[x]] then mx[x]:=mx[r];
end; procedure pushdown(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
if rev[x]> then
begin
rev[x]:=rev[x] xor ; rev[l]:=rev[l] xor ; rev[r]:=rev[r] xor ;
swap(t[x,],t[x,]);
end;
end; procedure rotate(x:longint);
var y,z,l,r:longint;
begin
y:=fa[x]; z:=fa[y];
if t[y,]=x then l:=
else l:=;
r:=l xor ;
if not isroot(y) then
begin
if t[z,]=y then t[z,]:=x
else t[z,]:=x;
end;
fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
t[y,l]:=t[x,r]; t[x,r]:=y;
pushup(y);
pushup(x);
end; procedure splay(x:longint);
var k,y,z:longint;
begin
inc(top); q[top]:=x;
k:=x;
while not isroot(k) do
begin
inc(top); q[top]:=fa[k];
k:=fa[k];
end;
while top> do
begin
pushdown(q[top]);
dec(top);
end; while not isroot(x) do
begin
y:=fa[x]; z:=fa[x];
if not isroot(y) then
begin
if (t[y,]=x)xor(t[z,]=y) then rotate(x)
else rotate(y);
end;
rotate(x);
end;
end; procedure access(x:longint);
var last:longint;
begin
last:=;
while x> do
begin
splay(x); t[x,]:=last; pushup(x);
last:=x; x:=fa[x];
end;
end; procedure makeroot(x:longint);
begin
access(x); splay(x); rev[x]:=rev[x] xor ;
end; procedure link(x,y:longint);
begin
makeroot(x); fa[x]:=y;
end; procedure split(x,y:longint);
begin
makeroot(x); access(y); splay(y);
end; procedure cut(x,y:longint);
begin
makeroot(x); access(y); splay(y); t[y,]:=; fa[x]:=;
end; function findroot(x:longint):longint;
var k:longint;
begin
access(x); splay(x);
k:=x;
while t[k,]<> do k:=t[k,];
exit(k);
end; begin
assign(input,'bzoj4736.in'); reset(input);
assign(output,'bzoj4736.out'); rewrite(output);
readln(n,m);
fillchar(w,sizeof(w),$7f);
//fillchar(l,sizeof(l),$1f);
for i:= to m do
begin
readln(ch); s:=; id:=; x:=; y:=; tt:=; ll:=;
len:=length(ch);
case ch[] of
'f':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:id:=id*+tmp;
:x:=x*+tmp;
:y:=y*+tmp;
:tt:=tt*+tmp;
:ll:=ll*+tmp;
end;
end;
inc(x); inc(y); inc(id);
tot:=id+;
w[tot]:=tt; l1[tot]:=ll; f[tot,]:=x; f[tot,]:=y;
if findroot(x)<>findroot(y) then
begin
mx[tot]:=tot;
link(x,tot); link(tot,y);
end
else
begin
split(x,y);
now:=mx[y];
if w[now]<tt then
begin
cut(f[now,],now); cut(now,f[now,]);
mx[tot]:=tot;
link(x,tot); link(tot,y);
end;
end; end;
'm':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:x:=x*+tmp;
:y:=y*+tmp;
end;
end;
inc(x); inc(y);
if findroot(x)<>findroot(y) then writeln(-)
else
begin
split(x,y); writeln(sum[y]);
end;
end;
'c':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:id:=id*+tmp;
:ll:=ll*+tmp;
end;
end;
inc(id); tot:=id+;
splay(tot);
l1[tot]:=ll;
pushup(tot);
end;
end;
end;
close(input);
close(output);
end.
2017.3.9
突然发现前一个代码splay打错了一个字母导致退化成类似单旋的东西
神TM单旋也能过
var t:array[..,..]of longint;
sum:array[..]of int64;
f:array[..,..]of longint;
w,l1,mx,fa,q,rev:array[..]of longint;
n,m,x,y,top,tot,id,i,len,s,ll,tt,j,tmp,now:longint;
ch:string; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; function isroot(x:longint):boolean;
begin
if (t[fa[x],]<>x)and(t[fa[x],]<>x) then exit(true);
exit(false);
end; procedure pushup(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
sum[x]:=sum[l]+sum[r]+l1[x];
mx[x]:=x;
if w[mx[l]]<w[mx[x]] then mx[x]:=mx[l];
if w[mx[r]]<w[mx[x]] then mx[x]:=mx[r];
end; procedure pushdown(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
if rev[x]> then
begin
rev[x]:=rev[x] xor ; rev[l]:=rev[l] xor ; rev[r]:=rev[r] xor ;
swap(t[x,],t[x,]);
end;
end; procedure rotate(x:longint);
var y,z,l,r:longint;
begin
y:=fa[x]; z:=fa[y];
if t[y,]=x then l:=
else l:=;
r:=l xor ;
if not isroot(y) then
begin
if t[z,]=y then t[z,]:=x
else t[z,]:=x;
end;
fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
t[y,l]:=t[x,r]; t[x,r]:=y;
pushup(y);
pushup(x);
end; procedure splay(x:longint);
var k,y,z:longint;
begin
inc(top); q[top]:=x;
k:=x;
while not isroot(k) do
begin
inc(top); q[top]:=fa[k];
k:=fa[k];
end;
while top> do
begin
pushdown(q[top]);
dec(top);
end; while not isroot(x) do
begin
y:=fa[x]; z:=fa[y];
if not isroot(y) then
begin
if (t[y,]=x)xor(t[z,]=y) then rotate(x)
else rotate(y);
end;
rotate(x);
end;
end; procedure access(x:longint);
var last:longint;
begin
last:=;
while x> do
begin
splay(x); t[x,]:=last; pushup(x);
last:=x; x:=fa[x];
end;
end; procedure makeroot(x:longint);
begin
access(x); splay(x); rev[x]:=rev[x] xor ;
end; procedure link(x,y:longint);
begin
makeroot(x); fa[x]:=y;
end; procedure split(x,y:longint);
begin
makeroot(x); access(y); splay(y);
end; procedure cut(x,y:longint);
begin
makeroot(x); access(y); splay(y); t[y,]:=; fa[x]:=;
end; function findroot(x:longint):longint;
var k:longint;
begin
access(x); splay(x);
k:=x;
while t[k,]<> do k:=t[k,];
exit(k);
end; begin
assign(input,'bzoj4736.in'); reset(input);
assign(output,'bzoj4736.out'); rewrite(output);
readln(n,m);
fillchar(w,sizeof(w),$7f);
//fillchar(l,sizeof(l),$1f);
for i:= to m do
begin
readln(ch); s:=; id:=; x:=; y:=; tt:=; ll:=;
len:=length(ch);
case ch[] of
'f':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:id:=id*+tmp;
:x:=x*+tmp;
:y:=y*+tmp;
:tt:=tt*+tmp;
:ll:=ll*+tmp;
end;
end;
inc(x); inc(y); inc(id);
tot:=id+;
w[tot]:=tt; l1[tot]:=ll; f[tot,]:=x; f[tot,]:=y;
if findroot(x)<>findroot(y) then
begin
mx[tot]:=tot;
link(x,tot); link(tot,y);
end
else
begin
split(x,y);
now:=mx[y];
if w[now]<tt then
begin
cut(f[now,],now); cut(now,f[now,]);
mx[tot]:=tot;
link(x,tot); link(tot,y);
end;
end; end;
'm':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:x:=x*+tmp;
:y:=y*+tmp;
end;
end;
inc(x); inc(y);
if findroot(x)<>findroot(y) then writeln(-)
else
begin
split(x,y); writeln(sum[y]);
end;
end;
'c':
begin
for j:= to len do
begin
if ch[j]=' ' then begin inc(s); continue; end;
tmp:=ord(ch[j])-ord('');
case s of
:id:=id*+tmp;
:ll:=ll*+tmp;
end;
end;
inc(id); tot:=id+;
splay(tot);
l1[tot]:=ll;
pushup(tot);
end;
end;
end;
close(input);
close(output);
end.
最新文章
- vim如何配置go语言环境
- SAE云平台上传图片和发送邮件
- （转）神经网络和深度学习简史（第一部分）：从感知机到BP算法
- tuning 02 Diagnostic and Tuning Tools
- ASP.Net 添加 Interop for Word, excel 插件
- Error prompt:“wget: unable to resolve host address”---Solution
- jq不识别拼接的对象id的解决方案
- file 上传文件后缀名 限制
- opencv---cvor
- HBase表创建、删除、清空
- jvm（四）：垃圾回收
- SQL——嵌套查询与子查询
- shell 批量获取ip 和主机名
- python学习第二次笔记
- codeforces611C
- mpvue构建小程序(步骤+地址)
- Windows Server 2008 R2 如何关闭防火墙
- typescript基础类型(学习笔记非干货)
- JavaBean之lombok
- python2编码的问题