|
|
back to boardCommon BoardCould anybody help mewith problem 1143? Isn't this finding of minimum spanning tree? Here is my program. 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... 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 > 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?(+) 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... This problem is finding the convex hull and calculate the perimeter, that's all :). So if your problem does that, you'r right > No, it isn't 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 (-) > > |
|
|