ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

Could anybody help mewith problem 1143? Isn't this finding of minimum spanning tree? Here is my program.
Послано Michael_Rybak 8 янв 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...
Послано Christopher Moh 8 янв 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
Послано Tran Nam Trung (trungduck@yahoo.com) 8 янв 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?(+)
Послано Michael_Rybak 8 янв 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!
Послано Li, Yi 8 янв 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...
Послано Michael_Rybak 8 янв 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
Послано Miguel Angel 9 янв 2002 11:17
>
No, it isn't
Послано Christopher Moh 9 янв 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 (-)
Послано Michael_Rybak 9 янв 2002 20:46
> >