POJ 1258

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