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

kruscal32Ms!

Posted by lijiaming456 at 2011-09-18 17:14:17 on Problem 2253
program ss;
type point=record
           x,y:longint;
           end;
     bian=record
          x,y:longint;
          w:double;
          end;

var a:array[1..200] of point;
    e:array[1..100000] of bian;
    father:array[1..200] of longint;
    i,j,k,m,n,s,t,x,y,z,l:longint;
    dist:double;

function get(x,y:longint):double;
begin
exit(sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y)));
end;

procedure qsort(l,r:longint);
var i,j,p:longint;
    t,mid:double;
begin
i:=l; j:=r; mid:=e[(l+r) shr 1].w;
repeat
while e[i].w<mid do inc(i);
while e[j].w>mid do dec(j);
if i<=j then
   begin
   p:=e[i].x; e[i].x:=e[j].x; e[j].x:=p;
   p:=e[i].y; e[i].y:=e[j].y; e[j].y:=p;
   t:=e[i].w; e[i].w:=e[j].w; e[j].w:=t;
   inc(i); dec(j);
   end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;

function getfather(v:longint):longint;
begin
if father[v]=v then exit(v);
father[v]:=getfather(father[v]);
exit(father[v]);
end;

begin
l:=0;
while true do
      begin
      readln(n); k:=0; inc(l);
      if n=0 then halt;
      for i:=1 to n do readln(a[i].x,a[i].y);
      for i:=1 to n do
          for j:=1 to n do
              if i<>j then
                 begin
                 dist:=get(i,j); inc(k);
                 with e[k] do
                      begin
                      e[k].x:=i; e[k].y:=j; e[k].w:=dist;
                      end;
                 end;
      for i:=1 to n do father[i]:=i;
      qsort(1,k);
      for i:=1 to k do
          begin
          x:=getfather(e[i].x);
          y:=getfather(e[i].y);
          father[x]:=y;
          getfather(1); getfather(2);
          if father[1]=father[2] then
             begin
             writeln('Scenario #',l);
             writeln('Frog Distance = ',e[i].w:0:3);
             writeln;
             break;
             end;
          end;
      end;
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