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.

Download