NKCITY - Xây dựng thành phố

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
var m,n,re:longint;
    cha,sl:array[1..1000] of longint;
    a,b,c:array[1..10000] of longint;

procedure rf;
var i:longint;
begin
      read(n,m);
      for i:=1 to m do read(a[i],b[i],c[i]);
end;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
        i:=l; j:=r; x:=c[(i+j) shr 1];
        repeat
              while c[i]<x do i:=i+1;
              while c[j]>x do j:=j-1;
              if i<=j then
              begin
                   y:=c[i]; c[i]:=c[j]; c[j]:=y;
                   y:=a[i]; a[i]:=a[j]; a[j]:=y;
                   y:=b[i]; b[i]:=b[j]; b[j]:=y;
                   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,x,y,dem:longint;
begin
     sort(1,m);
     for i:=1 to n do
     begin
        cha[i]:=i; sl[i]:=1;
     end;
     dem:=0; i:=0;
     repeat
           i:=i+1;
           x:=find(a[i]); y:=find(b[i]);
           if x<>y then
           begin
                inc(dem);
                if sl[x]>sl[y] then
                begin
                     cha[y]:=x;
                     sl[x]:=sl[x]+sl[y];
                end
                else
                begin
                     cha[x]:=y;
                     sl[y]:=sl[y]+sl[x];
                end;
           end;
     until dem=n-1;
     writeln(c[i]);
end;

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

Download