SSL P1618 剑鱼行动

算法：克鲁斯卡尔（Kruskal）
Description

给出N个点的坐标，对它们建立一个最小生成树，代价就是连接它们的路径的长度，现要求总长度最小。N的值在100以内，坐标值在[-10000,10000].结果保留二位小数

Input

5 —————5个点
0 0 —————5个点点的坐标
0 1
1 1
1 0
0.5 0.5

Output

2.83

解法：
1.先用勾股定理求出第i个点到第j个点的距离并储存在数组中。
2.克鲁斯卡尔（Kruskal）

vara:array [0..101,0..101] of extended;v:array [0..101] of longint;x,y:array [0..101] of extended;i,j,k,n,t,p,q:longint;min,ans:extended;
beginreadln(n);for i:=1 to n dobeginreadln(x[i],y[i]);v[i]:=i;end;for i:=1 to n dofor j:=1 to n doif i<>j thena[i,j]:=sqrt(abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]));for k:=1 to n-1 dobeginmin:=maxlongint;for i:=1 to n dofor j:=1 to n doif (v[i]<>v[j]) and (a[i,j]and (a[i,j]<>0) thenbeginmin:=a[i,j];p:=j;q:=i;end;ans:=ans+min;t:=v[p];for i:=1 to n do if v[i]=t then v[i]:=v[q];end;writeln(ans:0:2);
end.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！