//運(yùn)用prime 算法解決最小生成樹問題 :這里默認(rèn)從第一個(gè)頂點(diǎn)開始
//本題中要求輸出最終的最短路徑的和，所以將開始就有的路之間的邊長設(shè)為 0
//奉獻(xiàn)了好多次的WA 結(jié)果是因?yàn)樵趯⒁延羞叴嬖诘牡胤街辉O(shè)定了 edge[a][b]
= 0; 出錯(cuò)
本題的關(guān)鍵運(yùn)用在于輔助數(shù)組 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]; //開始時(shí)儲(chǔ)存源點(diǎn)到其他各頂點(diǎn)的邊值，隨后根據(jù)加進(jìn)來的頂點(diǎn)，不斷改變所存的邊值
10 int edge[101][101]; //存輸入的邊之間的長度
11 int visit[101]; //標(biāo)志頂點(diǎn)是否已經(jīng)加入
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 ++) //本身存在邊則該頂點(diǎn)被標(biāo)記
30 {
31 scanf ("%d %d", &a, &b);
32 edge[a][b] = edge[b][a] = 0;
33 }
34 }
35
36 //prime:每次都從剩下的邊中選出最短的一條，標(biāo)記相關(guān)的頂點(diǎn)，并且修改相關(guān)邊的值
37 //對lowcost 進(jìn)行初始化處理
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) //如果沒有找到最小的邊一下一個(gè)頂點(diǎn)作為起點(diǎn)
59 break;
60
61 visit[k] = 1;
62 sum += lowcost[k];
63
64 //修改要加入的頂點(diǎn)到其他未加入頂點(diǎn)之間的距離
for (int i = 1; i <= n; i ++)
65 {
66 if ( !visit[i] && lowcost[i] > edge[k][i]) //新引入的頂點(diǎn)到其他頂點(diǎn)的邊值 是否 小于 原來的邊值
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
雪黛依夢 閱讀(359)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
最小生成樹