和 1102 完全一個類型的，只是調用幾個數學函數求距離
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 15:35
雪黛依夢 閱讀(448)
評論(0) 編輯 收藏 引用 所屬分類:
最小生成樹