NKRACING - Vòng đua F1

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      maxn=10010;
      maxm=100010;
var re,n,m:longint;
    b:array[0..maxm,0..2] of longint;
    cha,sl:array[1..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     read(n,m);
     for i:=1 to m do
         for j:=0 to 2 do
             read(b[i,j]);
     for i:=1 to n do
     begin
          cha[i]:=i; sl[i]:=1;
     end;
end;

procedure sort(l,r:longint);
var i,j,x:longint;
begin
     i:=l; j:=r; x:=b[(i+j) shr 1,2];
     repeat
           while b[i,2]>x do i:=i+1;
           while b[j,2]<x do j:=j-1;
           if i<=j then
           begin
                b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function find(x:longint):longint;
begin
     if cha[x]=x then find:=x
     else
     begin
          cha[x]:=find(cha[x]);
          find:=cha[x];
     end;
end;

procedure pr;
var i,j,x,y,xx,yy,dem:longint;
begin
     sort(1,m);
     for i:=1 to m do
     begin
          x:=b[i,0]; y:=b[i,1];
          xx:=find(x); yy:=find(y);
          if xx=yy then re:=re+b[i,2]
          else
          begin
               dem:=dem+1;
               if sl[xx]>=sl[yy] then
               begin
                    cha[yy]:=xx;
                    sl[xx]:=sl[xx]+sl[yy];
               end
               else
               begin
                    cha[xx]:=yy;
                    sl[yy]:=sl[yy]+sl[xx];
               end;
               if dem=n-1 then break;
          end;
     end;
     for j:=i+1 to m do re:=re+b[j,2];
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download