- 口袋的天空
- 2009-07-30 22:30:29 @
const
max=32767;
var
a:array[0..1000,0..1000]of integer;
last:integer;
i:integer;
n,m,k:integer;
visit:array[0..1000]of boolean;
ans:integer;
b:array[0..1000]of integer;
lowcost,closst:array[0..1000] of integer;
procedure init;
var
i,j,x,y,l:integer;
begin
readln(n,m,k);
for i:=1 to n do
for j:=1 to n do
a:=max;
for i:=1 to m do
begin
readln(x,y,l);
a[x,y]:=l;
a[y,x]:=l;
end;
end;
procedure prim(x:integer);
var
j,t,i:integer;
min:integer;
begin
for j:=1 to n do
if visit[j] then
begin
lowcost[j]:=a[x,j];
closst[j]:=x;
end;
lowcost[x]:=0;
visit[x]:=false;
min:=max;
for j:=2 to n do
begin
i:=0;
for t:=1 to n do
if (lowcost[t]a)and(a0)then
begin lowcost[t]:=a;closst[t]:=i;end;
end;
end;
end;
procedure qsort(l,r:integer);
var
x:integer;
i,j:integer;
p:integer;
begin
x:=b[(l+r)shr 1];
i:=l;
j:=r;
repeat
while b[i]>x do inc(i);
while b[j]n then begin writeln('No Answer');exit;end;
if k=n then begin writeln(0);exit;end;
fillchar(visit,sizeof(visit),true);
last:=0;
for i:=1 to n do
if visit[i] then
begin inc(ans);prim(i);end;
qsort(1,last);
if n-(last+ans)>k then begin writeln('No Answer');exit;end;
for i:=1 to k-(n-(last+ans))-ans do
b[i]:=0;
ans:=0;
for i:=1 to last do ans:=ans+b[i];
writeln(ans);
end.
这样不对吗?