VNEMPIRE - Đế chế
Tác giả: ladpro98
Ngôn ngữ: Pascal
{$MODE OBJFPC}
program vnempire;
uses math;
const maxn=100005;
maxm=6*maxn;
fi='';
type e=record
x,y,w:longint;
end;
point =record
v,p:longint;
end;
arr=array[1..maxn] of point;
var x,y,z:arr;
inp:text;
n,m,k,res,i,xx,yy:longint;
ed:array[1..maxm] of e;
lab:array[1..maxn] of longint;
procedure sort(var a:arr; l,r:longint);
var p,i,j:longint;
t:point;
begin
if l>=r then exit;
i:=l;j:=r;
p:=a[random(r-l+1)+l].v;
repeat
while a[i].v<p do inc(i);
while a[j].v>p do dec(j);
if i<=j then
begin
if i<j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sort(a,l,j);sort(a,i,r);
end;
procedure sortE(l,r:longint);
var p,i,j:longint;
t:e;
begin
if l>=r then exit;
i:=l;j:=r;
p:=ed[random(r-l+1)+l].w;
repeat
while ed[i].w<p do inc(i);
while ed[j].w>p do dec(j);
if i<=j then
begin
if i<j then
begin
t:=ed[i];
ed[i]:=ed[j];
ed[j]:=t;
end;
inc(i);
dec(j);
end;
until i>j;
sortE(l,j);sortE(i,r);
end;
function root(u:longint):longint;
begin
if lab[u]<=0 then exit(u);
result:=root(lab[u]);
lab[u]:=result;
end;
procedure union(u,v:longint);
begin
if lab[u]<lab[v] then lab[v]:=u
else
begin
if lab[u]=lab[v] then dec(lab[v]);
lab[u]:=v;
end;
end;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
for i:=1 to n do
begin
readln(inp,x[i].v,y[i].v,z[i].v);
x[i].p:=i;y[i].p:=i;z[i].p:=i;
end;
sort(x,1,n);sort(y,1,n);sort(z,1,n);
for i:=2 to n do
begin
inc(m);
ed[m].x:=x[i].p;ed[m].y:=x[i-1].p;ed[m].w:=abs(x[i].v-x[i-1].v);
inc(m);
ed[m].x:=y[i].p;ed[m].y:=y[i-1].p;ed[m].w:=abs(y[i].v-y[i-1].v);
inc(m);
ed[m].x:=z[i].p;ed[m].y:=z[i-1].p;ed[m].w:=abs(z[i].v-z[i-1].v);
end;
sortE(1,m);
for i:=1 to m do
begin
xx:=root(ed[i].x);
yy:=root(ed[i].y);
if xx<>yy then
begin
union(xx,yy);
inc(res,ed[i].w);
inc(k);
end;
if k=n-1 then break;
end;
write(res);
end.