NKRACING - Vòng đua F1

Tác giả: ladpro98

Ngôn ngữ: Pascal

{$MODE OBJFPC}
program nkracing;
uses    math;
type    e=record
        x,y,w:longint;
        end;
const   maxn=10004;
        maxm=100005;
        fi='';
var     res,n,m:longint;
        a:array[1..maxm] of e;
        lab:array[1..maxn] of longint;
        check:array[1..maxm] of boolean;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        readln(inp,a[i].x,a[i].y,a[i].w);
        close(inp);
end;

procedure sort(l,r:longint);
var     p,i,j:longint;
        t:e;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=a[random(r-l+1)+l].w;
        repeat
                while a[i].w>p do inc(i);
                while a[j].w<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(l,j);sort(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;

procedure kruskal;
var     i,x,y,c:longint;
begin
        sort(1,m);
        for i:=1 to m do
        begin
                x:=root(a[i].x);
                y:=root(a[i].y);
                if x<>y then
                begin
                        inc(c);
                        check[i]:=true;
                        union(x,y);
                end;
                if c=n-1 then break;
        end;
        for i:=1 to m do if not check[i] then inc(res,a[i].w);
end;

begin
        input;
        kruskal;
        write(res);
end.

Download