Posted on 2008-06-05 16:44
superman 閱讀(203)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1372 C++ 00:00.33 848K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, map[50][50];
9
10 while(cin >> n >> m)
11 {
12 for(int i = 0; i < n; i++)
13 for(int j = 0; j < n; j++)
14 map[i][j] = INT_MAX;
15
16 int s, t, l;
17 for(int i = 0; i < m; i++)
18 {
19 cin >> s >> t >> l;
20 s--, t--;
21 if(l < map[s][t] && l < map[t][s])
22 map[s][t] = map[t][s] = l;
23 }
24
25 if(n == 0 || m == 0)
26 {
27 cout << 0 << endl; continue;
28 }
29
30 //prim
31 int ans = 0;
32 int lowcost[50];
33 bool vset[50] = { true };
34
35 for(int i = 1; i < n; i++)
36 lowcost[i] = map[0][i];
37 int v = 0;
38 for(int k = 1; k < n; k++)
39 {
40 int min = INT_MAX, idx;
41 for(int i = 0; i < n; i++)
42 if(vset[i] == false && lowcost[i] < min)
43 min = lowcost[i], idx = i;
44
45 vset[idx] = true;
46 v = idx;
47
48 ans += min;
49
50 for(int i = 0; i < n; i++)
51 if(vset[i] == false && map[v][i] < lowcost[i])
52 lowcost[i] = map[v][i];
53 }
54
55 cout << ans << endl;
56 }
57
58 return 0;
59 }
60