- Kerry 的电缆网络
- 2009-08-10 13:04:57 @
var a:array[0..100000,1..2] of longint;
v:array[0..100000] of longint;
s:array[0..100000] of real;
ans:boolean;
smin,smax:real;
i,j,n,m:longint;
procedure Qsort(x,y:longint);
var l,r,k:longint;
begin
l:=x; r:=y;
k:=(x+y) div 2;
repeat
while s[l]s[k] do dec(r);
if lr;
if lx then Qsort(x,r);
end;
function root(x:longint):longint;
begin
if v[x]=x then root:=x
else begin
root:=root(v[x]);
v[x]:=root;
end;
end;
procedure union(l,r:longint);
begin
l:=root(l); r:=root(r);
v[l]:=r;
end;
begin
readln(smax);
readln(n);
m:=1;
repeat
readln(a[m,1],a[m,2],s[m]);
inc(m);
until eof;
dec(m);
Qsort(1,m);
for i:=1 to n do v[i]:=i;
smin:=0;
for i:=1 to m do
if root(a)root(a) then begin
union(a,a);
smin:=smin+s[i];
end;
ans:=true;
for i:=1 to n do if v[i]v[1] then ans:=false;
if (smax>smin) and (ans) then write('Need ',smin:0:2,' miles of cable')
else write('Impossible');
end.
3 条评论
-
w82650592 LV 8 @ 2009-08-14 13:36:17
谢了
谢了啊。。。
但是改了还是只过2个点 -
2009-08-11 10:22:58@
这个快排不大好呵。
我在给你一个新的吧。
procedure sort(s,m:longint);
var i,j,x:longint;
begin
i:=s; j:=m; x:=a[i];
repeat
while (ix) do dec(j);
if i -
2009-08-10 16:38:46@
回复
快排中.
k=(x+y)div 2
改为
k=s[(x+y)div 2]
并在后面做相应的调整
- 1