ac1244.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1244;
const
  maxn=300;
  maxc=10000;
var
  v1,v2,order:array[1..maxc]of word;
  len:array[1..maxc]of longint;
  root:array[1..maxn]of word;
  n,c,i,r,a,b:longint;
procedure qsort(s,t:word);
  var
    p,i,j,torder,tlen:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    torder:=order[p];order[p]:=order[s];tlen:=len[torder];
    i:=s;j:=t;
    repeat
      while (i<j) and (len[order[j]]>=tlen) do dec(j);
      if i=j then break;order[i]:=order[j];inc(i);
      while (i<j) and (len[order[i]]<=tlen) do inc(i);
      if i=j then break;order[j]:=order[i];dec(j);
    until i=j;
    order[i]:=torder;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure pathcomp(x:word);
  var
    r,t:word;
  begin
    r:=x;while root[r]<>r do r:=root[r];
    while x<>r do begin t:=root[x];root[x]:=r;x:=t;end;
  end;
begin
  repeat
    read(n,c);
    for i:=1 to c do begin read(v1[i],v2[i],len[i]);order[i]:=i;end;
    qsort(1,c);
    for i:=1 to n do root[i]:=i;r:=n;
    for i:=1 to c do begin
      a:=v1[order[i]];b:=v2[order[i]];
      pathcomp(a);pathcomp(b);
      if root[a]<>root[b] then begin
        root[root[a]]:=root[b];
        dec(r);if r=1 then begin writeln(n-1,' ',len[order[i]]);break;end;
      end;
    end;
  until seekeof;
end.