noip最优贸易用pascal的链式前向星做求代码
发布网友
发布时间：2023-10-18 01:45
共2个回答
热心网友
时间：2024-12-01 00:03
var
i,n,m,ans,xx,yy,mmax,mmin:longint;
x,y,z:array[0..500000] of longint;
a,f,max,min,g:array[0..100000] of longint;
v:array[0..100000] of boolean;
function find(t:longint):longint;
begin
if f[t]<>t then find:=find(f[t])
else find:=t;
f[t]:=find;
end;
procere init;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
read(x[i],y[i],z[i]);
if z[i]=2 then f[find(x[i])]:=find(y[i]);
end;
for i:=1 to n do
begin
max[i]:=a[i];
min[i]:=a[i];
end;
for i:=1 to m do
begin
xx:=find(x[i]);
yy:=find(y[i]);
if a[x[i]]>max[xx] then max[xx]:=a[x[i]];
if a[x[i]]<min[xx] then min[xx]:=a[x[i]];
if a[y[i]]>max[yy] then max[yy]:=a[y[i]];
if a[y[i]]<min[yy] then min[yy]:=a[y[i]];
if z[i]=2 then
begin
if a[x[i]]>max[yy] then max[yy]:=a[x[i]];
if a[x[i]]<min[yy] then min[yy]:=a[x[i]];
if a[y[i]]>max[xx] then max[xx]:=a[y[i]];
if a[y[i]]<min[xx] then min[xx]:=a[y[i]];
end;
x[i]:=xx;
y[i]:=yy;
end;
end;
procere sort(l,r:longint);
var
i,j,ix,iy:longint;
begin
i:=l;
j:=r;
ix:=x[(l+r)shr 1];
repeat
while x[i]<ix do inc(i);
while ix<x[j] do dec(j);
if i<=j then
begin
iy:=x[i];
x[i]:=x[j];
x[j]:=iy;
iy:=y[i];
y[i]:=y[j];
y[j]:=iy;
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procere dfs1(k:longint);
var
j:longint;
begin
min[k]:=mmin;
if k=n then exit;
if v[k] then exit;
v[k]:=true;
for j:=g[k-1] to g[k]-1 do
begin
if mmin>min[y[j]] then mmin:=min[y[j]];
dfs1(y[j]);
mmin:=min[k];
end;
end;
procere dealmin;
begin
sort(1,m);
for i:=1 to m+1 do
if x[i]<>x[i-1] then g[x[i-1]]:=i;
for i:=1 to n do if g[i]=0 then g[i]:=g[i-1];
g[0]:=1;
mmin:=min[1];
dfs1(1);
end;
procere qsort(l,r:longint);
var
i,j,ix,iy:longint;
begin
i:=l;
j:=r;
ix:=y[(l+r)shr 1];
repeat
while y[i]<ix do inc(i);
while ix<y[j] do dec(j);
if i<=j then
begin
iy:=x[i];
x[i]:=x[j];
x[j]:=iy;
iy:=y[i];
y[i]:=y[j];
y[j]:=iy;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procere dfs2(k:longint);
var
j:longint;
begin
max[k]:=mmax;
if (max[k]-min[k]>ans) then ans:=max[k]-min[k];
if k=1 then exit;
if v[k] then exit;
v[k]:=true;
for j:=g[k-1] to g[k]-1 do
begin
if mmax<max[x[j]] then mmax:=max[x[j]];
dfs2(x[j]);
mmax:=max[k];
end;
end;
procere dealmax;
begin
qsort(1,m);
fillchar(g,sizeof(g),0);
fillchar(v,sizeof(v),false);
for i:=1 to m+1 do
if y[i]<>y[i-1] then g[y[i-1]]:=i;
for i:=1 to n do if g[i]=0 then g[i]:=g[i-1];
g[0]:=1;
mmax:=max[n];
dfs2(n);
end;
begin
init;
dealmin;
dealmax;
writeln(ans);
end.
热心网友
时间：2024-12-01 00:03
请给出完整描述。
