ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

Could anybody help mewith problem 1143? Isn't this finding of minimum spanning tree? Here is my program.
Posted by Michael_Rybak 8 Jan 2002 15:22
Could anybody tell me what's wrong with this code?
{$N+}
Program ElectricPath;
 Const Max=200;
 Type TEdge=Record
       p1,p2:Byte;
       sl:Extended;
      End;
 Var a,b:Array[1..Max*Max] Of TEdge;
     ne,n:Longint;
     x,y:Array[1..Max] Of Extended;
     canget:Array[1..Max,1..Max] Of Boolean;
     an:Extended;
 Procedure Sort(x,y:Longint);
  Var z:Longint;
  Procedure Merge;
   Var p,p1,p2:Longint;
  Begin
   p1:=x; p2:=z+1; p:=0;
   While ((p1<=z) Or (p2<=y)) Do Begin
    Inc(p);
    If p1<=z Then Begin
     b[p]:=a[p1];
     Inc(p1);
     If p2<=y Then
      If a[p2].sl<b[p].sl Then Begin
       b[p]:=a[p2];
       Inc(p2);
       Dec(p1);
      End;
    End Else Begin
     b[p]:=a[p2];
     Inc(p2);
    End;
   End;
   For p:=x To y Do
    a[p]:=b[p-x+1];
  End;
 Begin
  If x<y Then Begin
   z:=(x + y) Div 2;
   Sort(x,z);
   Sort(z+1,y);
   Merge;
  End;
 End;
 Procedure AddEdge(i,j:Longint);
  Var x1,y1,x2,y2:Extended;
 Begin
  Inc(ne);
  With a[ne] Do Begin
   p1:=i; p2:=j;
   x1:=x[i];
   y1:=y[i];
   x2:=x[j];
   y2:=y[j];
   sl:=((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  End;
 End;
 Procedure ReadData;
  Var i,j:Longint;
 Begin
  Read(n);
  For i:=1 To n Do Begin
   Read(x[i],y[i]);
   For j:=1 To i-1 Do
    AddEdge(i,j);
  End;
 End;
 Procedure Proceed;
  Var i:Longint;
  Procedure NowCanGet(p1,p2:Longint);
   Var i,j:Longint;
  Begin
   For i:=1 To n Do
    If canget[i,p1] Then
     For j:=1 To n Do
      If canget[j,p2] Then Begin
       canget[i,j]:=True;
       canget[j,i]:=True;
      End;
  End;
 Begin
  FillChar(canget,SizeOf(canget),False);
  For i:=1 To n Do
   canget[i,i]:=True;
  an:=0;
  For i:=1 To ne Do
   With a[i] Do
    If Not canget[p1,p2] Then Begin
     NowCanGet(p1,p2);
     an:=an+Sqrt(sl);
    End;
 End;
Begin
 ne:=0;
 ReadData;
 Sort(1,ne);
 Proceed;
 Writeln(an:0:3);
End.
I haven't read your program yet but the soln is NOT to find the MST...
Posted by Christopher Moh 8 Jan 2002 17:03
the solution is to find the minimal PATH:

i.e. every node except the starting and ending nodes are connected to
exactly two other nodes in the path.
re: Right, the solution is DP not MST
Posted by Tran Nam Trung (trungduck@yahoo.com) 8 Jan 2002 17:16
> the solution is to find the minimal PATH:
>
> i.e. every node except the starting and ending nodes are connected
to
> exactly two other nodes in the path.
Unfortunately, I still don't understand what do I have to do. Could you please explain the task on some test?(+)
Posted by Michael_Rybak 8 Jan 2002 18:25
Or could you explain the task with another words maybe? What does it
mean - the shortest path?
It is a path, not a tree!
Posted by Li, Yi 8 Jan 2002 19:05
> Or could you explain the task with another words maybe? What does
it
> mean - the shortest path?
Thank you all, I get AC! By the way, I don't know how to prove that my solution is correct...
Posted by Michael_Rybak 8 Jan 2002 21:12
This problem is finding the convex hull and calculate the perimeter, that's all :). So if your problem does that, you'r right
Posted by Miguel Angel 9 Jan 2002 11:17
>
No, it isn't
Posted by Christopher Moh 9 Jan 2002 12:06
Already the solution to the sample input is NOT the convex hull...
It is certainly NOT that kind of problem. I have a VERY greedy algorythm, but it seems to be correct (-)
Posted by Michael_Rybak 9 Jan 2002 20:46
> >