//运用prime 算法解决最小生成树问题 :这里默认从第一个顶点开始
//本题中要求输出最终的最短路径的和，所以将开始就有的路之间的边长设为 0
//奉献了好多次的WA 结果是因为在将已有边存在的地方只设定了 edge[a][b]
= 0; 出错
本题的关键运用在于辅助数组 lowcost[ ] 的使用
1
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6int main ()
7
{
8
int n, q, a, b;
9 int lowcost[101]; //开始时储存源点到其他各顶点的边值，随后根据加进来的顶点，不断改变所存的边值
10 int edge[101][101]; //存输入的边之间的长度
11 int visit[101]; //标志顶点是否已经加入
12
13 while ( scanf ("%d", &n)!= EOF )
14
{
15 memset (visit, 0, sizeof (visit));
16 memset (lowcost, 0, sizeof (lowcost));
17
18 //输入处理
19 for (int i = 1; i <= n; i ++)
20 {
21 for (int j = 1; j<= n; j ++)
22 {
23 scanf ("%d", &edge[i][j]);
24
}
25 }
26 scanf ("%d", &q);
27 if ( q )
28 {
29 for (int i = 0; i < q; i ++) //本身存在边则该顶点被标记
30 {
31 scanf ("%d %d", &a, &b);
32 edge[a][b] = edge[b][a] = 0;
33 }
34 }
35
36 //prime:每次都从剩下的边中选出最短的一条，标记相关的顶点，并且修改相关边的值
37 //对lowcost 进行初始化处理
38 for (int i = 1; i <= n; i ++ )
39 {
40 lowcost[i] = edge[1][i];
41 }
42
43 int sum = 0;
44 int k;
45 for (int i = 1; i <= n; i ++)
46 {
47 int max = 10000;
48
49 for ( int i = 1; i <= n; i ++ )
50 {
51 if ( lowcost[i] < max && !visit[i] )
52 {
53 max = lowcost[i];
54 k = i;
55 }
56 }
57
58 if (max == 10000) //如果没有找到最小的边一下一个顶点作为起点
59 break;
60
61 visit[k] = 1;
62 sum += lowcost[k];
63
64 //修改要加入的顶点到其他未加入顶点之间的距离
for (int i = 1; i <= n; i ++)
65 {
66 if ( !visit[i] && lowcost[i] > edge[k][i]) //新引入的顶点到其他顶点的边值 是否 小于 原来的边值
67 {
68 lowcost[i] = edge[k][i];
69 }
70 }
71 }
72 printf ("%d\n", sum);
73 }
74 // system ("pause");
75 return 0;
76
}
77
posted on 2010-08-23 14:06
雪黛依梦 阅读(340)
评论(0) 编辑 收藏 引用 所属分类:
最小生成树