[BZOJ1791] [IOI2008] Island 베이스 링 외향수 + DP
type
edge=^edgenode;
edgenode=record
t,w:longint;
next:edge;
end;
node=record
t:longint;
w:int64;
end;
const maxn=1000100;
var
n,i,j,x,y,num,top,oncir:longint;
ans,all:int64;
con:array[0..maxn]of edge;
visit,cir:array[0..maxn]of boolean;
huan:array[0..maxn]of longint;
nt:array[0..maxn]of node;
g,dis:array[0..2*maxn]of int64;
dl:array[0..2*maxn]of node;
procedure ins(x,y,w:longint);
var
p:edge;
begin
new(p);
p^.t:=y;
p^.w:=w;
p^.next:=con[x];
con[x]:=p;
end;
function max(x,y:int64):int64;
begin
if x>y then exit(x)
else exit(y);
end;
procedure findcir(v:longint);
var
p:edge;
begin
visit[v]:=true;
if visit[nt[v].t]=false then findcir(nt[v].t)
else oncir:=nt[v].t;
if oncir>0 then begin inc(top); huan[top]:=v; cir[v]:=true; end;
if oncir=v then oncir:=0;
visit[v]:=false;
end;
function dfs(v:longint):int64;
var
p:edge;
now,o:int64;
begin
p:=con[v];
dfs:=0;
now:=0;
visit[v]:=true;
while p<>nil do
begin
if cir[p^.t]=false then
begin
o:=dfs(p^.t)+p^.w;
dfs:=max(dfs,o);
ans:=max(ans,o+now);
now:=max(now,o);
end;
p:=p^.next;
end;
end;
procedure dp;
var
i,j,head,tail:longint;
begin
head:=1;
tail:=0;
for i:=1 to 2*top-1 do
begin
while (head<=tail)and(dl[head].t<=i-top) do inc(head);
if i>=top then ans:=max(ans,dl[head].w+g[i]+dis[i]);
while (head<=tail)and(g[i]-dis[i]>=dl[tail].w) do dec(tail);
inc(tail);
dl[tail].t:=i;
dl[tail].w:=g[i]-dis[i];
end;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(x,y);
nt[i].t:=x;
nt[i].w:=y;
ins(x,i,y);
end;
fillchar(visit,sizeof(visit),false);
fillchar(cir,sizeof(cir),false);
for i:=1 to n do
if visit[i]=false then
begin
oncir:=0;
top:=0;
ans:=0;
findcir(i);
for j:=1 to top do
g[j]:=dfs(huan[j]);
for j:=1 to top-1 do
begin
g[j+top]:=g[j];
huan[j+top]:=huan[j];
end;
dis[1]:=0;
for j:=2 to 2*top-1 do
dis[j]:=dis[j-1]+nt[huan[j]].w;
dp;
all:=all+ans;
end;
write(all);
end.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.