POJ 1287

 1 #include<iostream>
 2 #include<stdio.h>
 3 #define MAXN 100
 4 #define inf 1000000000
 5 using namespace std;
 6 int _m[MAXN][MAXN];
 7 int pre[MAXN];
 8 int low_cost[MAXN];
 9 int prime(int n);
10 int main()
11 {
12 //    freopen("acm.acm","r",stdin);
13     int point;
14     int edge;
15     int i;
16     int j;
17     int u;
18     int v;
19     int temp;
20     while(cin>>point>>edge)
21     {
22         for(i = 0; i < point; ++ i)
23         {
24             for(j = 0; j < point; ++ j)
25             {
26                 _m[i][j] = inf;
27             }
28         }
29         for(i = 0; i < edge; ++ i)
30         {
31             cin>>u>>v;
32             --u;
33             --v;
34             if(_m[u][v] == 0)
35             {
36                 cin>>_m[u][v];
37                 _m[v][u] = _m[u][v];
38             }
39             else
40             {
41                 cin>>temp;
42                 if(_m[u][v] > temp)
43                 {
44                     _m[u][v] = temp;
45                     _m[v][u] = temp;
46                 }
47             }
48         }
49         cout<<prime(point)<<endl;
50     }
51 }
52 
53 
54 int prime(int n)
55 {
56     int i;
57     int j;
58     int k;
59     int sum = 0;
60     int min;
61     for(i = 1; i < n; ++ i)
62     {
63         low_cost[i] = _m[0][i];
64         pre[i] = 0;
65     }
66     for(i = 1; i < n; ++ i)
67     {
68         min = inf;
69         for(j = 1; j < n; ++ j)
70         {
71             if(low_cost[j]&&low_cost[j] < min)
72             {
73                 k = j;
74                 min = low_cost[j];
75             }
76         }
77         sum += low_cost[k];
78         low_cost[k] = 0;
79         for(j = 1; j < n; ++ j)
80         {
81             if(_m[k][j] < low_cost[j] && low_cost[j])
82             {
83                 low_cost[j] = _m[k][j];
84                 pre[j] = k;
85             }
86         }
87     }
88     return sum;
89 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com