Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Kruskal算法解2395刷新纪录,用时0MS,求点击,附PASCAL代码

Posted by liyounan at 2011-01-21 11:03:02 on Problem 2395
program poj2395;
type
  node=record
    fromv,endv:integer;
    weight:longint;
  end;
var
  e:array[1..10000] of node;
  s:array[1..2000] of integer;
  n,m,i,j,k,sum:longint;
procedure quick(h,r:integer);
var
  i,j:integer;
  x,t:longint;
begin
  i:=h;j:=r;x:=e[(i+j)div 2].weight;
  while i<j do
  begin
    while e[i].weight<x do inc(i);
    while e[j].weight>x do dec(j);
    if i<=j then
    begin
      t:=e[i].weight; e[i].weight:=e[j].weight; e[j].weight:=t;
      t:=e[i].fromv;  e[i].fromv:=e[j].fromv;   e[j].fromv:=t;
      t:=e[i].endv;   e[i].endv:=e[j].endv;     e[j].endv:=t;
      inc(i);
      dec(j);
    end;
  end;
 if i<r then quick(i,r);
 if j>h then quick(h,j);
end;
function find(v:integer):integer;
begin
  if s[v]=v then find:=v
  else
  begin
    s[v]:=find(s[v]);
    find:=s[v];
  end;
end;
begin
  readln(n,m);
  for i:=1 to m do
   readln(e[i].fromv,e[i].endv,e[i].weight);
  quick(1,m);
  for i:=1 to n do s[i]:=i;
  i:=1;
  j:=1;
  sum:=0;
  while i<=n-1 do
  begin
     if find(e[j].fromv)<>find(e[j].endv) then
     begin
       s[find(e[j].fromv)]:=find(e[j].endv);
       inc(i);
       if e[j].weight>sum then sum:=e[j].weight;
     end;
     inc(j);
  end;
  writeln(sum);
end.


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator