题意:
Eddy画了画像,由几个点组成,求解出能把所有点连接在一起所需要的最短线的和。
这一题所涉及的内容是最小生成树,求解最小生成树的方法可以使用普林姆和克鲁斯卡尔两种方法,
这里介绍一下普林姆算法的思想。
假设有如下图1:
点集a1 = {a,b,c,d,e},a2为空集,普林姆算法需要空集a2加入点集a1中的点,同时集合a1去
掉该点,直至a1为空集。假设我们从点a开始加入,下面用图像分步展示操作步骤:
第一步:把节点集合a1中的节点a加入a2中构成一棵树,同时去掉a1中的点a,此时a1 = {b,c,d,e},
a2 = {a}。
第二步:搜索a1中的全部节点找到a1中到a2集合中的最小距离,即找到找到a1中的所有节点到这棵生成
树的最小距离。所以找到了d点。
第三步、第四步、第五步:继续重复第二步的操作,直到所有的点都构成一棵生成树。最终第五步生成了一
棵最小生成树。
这道题目使用这种方法就可以解决了。以下就是我的C语言实现代码:
#include <stdio.h> #include <math.h> #include <string.h> #define MAXN 110 double map[MAXN][MAXN]; int used[MAXN];//标记数组 struct{ double x; double y; }node[MAXN];//保存节点信息 double prim (int n) { int i,j; int y; double sum = 0; used[0] = 1; while (1) { int flag = 0; double min = 100000000; for (i = 0; i < n; i++) { if(!used[i]) {//判断是否还有点未被标记,即是否在a1数组中 flag = 1; break; } } if (flag) { for (i = 0; i < n; i++) { if (used[i]) {//判断该点是否在a2数组中 for (j = 0; j < n; j++) { if (map[i][j] < min && i != j && !used[j]) { min = map[i][j]; y = j;//保存节点的位置 } } } } used[y] = 1; sum += min; } else { return sum; } } } int main () { int n; int i,j; while (scanf("%d",&n) != EOF) { memset (used, 0, sizeof (used)); for (i = 0; i < n; i++) { scanf ("%lf%lf",&node[i].x,&node[i].y); } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { map[i][j] = map[j][i] = sqrt ((node[i].x - node[j].x) * (node[i].x - node[j].x) + (node[i].y - node[j].y) * (node[i].y - node[j].y)); } } printf ("%.2lf\n",prim (n)); } return 0; }