最后一个点WA,大神来找错

var father,x,y:array[0..1000005] of longint;ss:array[0..1000005] of double; n,m,i,root2,root1,roo2:longint;ans,s:double;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
procedure swap1(var a,b:double);
var t:double;
begin
t:=a;
a:=b;
b:=t;
end;
procedure sort(l,r: longint);
var
i,j:longint; mid:double;
begin
i:=l;
j:=r;
mid:=ss[random(r-l+1)+l];
while i<j do
begin
while ss[i]<mid do
inc(i);
while mid<ss[j] do
dec(j);
if not(i>j) then
begin
swap1(ss[i],ss[j]);
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);
j:=j-1;
end;
end;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

function find(x:longint):longint;
begin
if father[x]<>x then father[x]:=find(father[x]);
exit(father[x]);
end;
procedure union(x,y:longint);
begin
father[y]:=x;
end;
begin
readln(s);
readln(n);
for i:=1 to n do
father[i]:=i;
m:=0;
while not eof do
begin
inc(m);
readln(x[m],y[m],ss[m]);
end;
sort(1,m);
for i:=1 to m do
begin
root1:=find(x[i]);
root2:=find(y[i]);
if root1<>root2 then
begin
union(root1,root2);
ans:=ans+ss[i];
end;
end;
if ans>s then writeln('Impossible')
else writeln('Need ',ans:0:2,' miles of cable');
end.

0 条评论

目前还没有评论...

信息

ID
1045
难度
7
分类
树结构 点击显示
标签
(无)
递交数
4932
已通过
1000
通过率
20%
被复制
10
上传者