qbqwer 2009-08-02 02:03:00
点我顶贴
收藏
删除
program rq370；
var a:array[0..100,0..100] of integer；
i,j,k,m,n,min,tot:integer；
b:array[1..100]of integer；
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
begin
tot:=0；
readln(n,k)；
for i:=1 to n do
for j:=1 to n do
a[i,j]:=maxint；
for m:=1 to k do
begin
read(i,j)；
readln(a[i,j])；
a[j,i]:=a[i,j]；
inc(tot,a[j,i])；
end；
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
for i:=1 to n do
b[i]:=a[1,i]；
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点 k}
min:=maxint；
for j:=1 to n do
if (b[j]<min) and (b[j]<>0) then begin
min:=b[j]；
k:=j；
end；
dec(tot,min)；
b[k]:=0； {将顶点k 加入生成树}
{生成树中增加一条新的边 k 到 closest[k]}
{修正各点的 b 和 closest 值}
for j:=1 to n do
if a[k,j]<b[j] then
b[j]:=a[k,j]；
end；
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
writeln(tot)；
end.