1 #include<stdio.h>
2 #define MAXN 1005
3 #include<iostream>
4 #include<algorithm>
5 #define inf 10000000
6 using namespace std;
7 int _m[MAXN][MAXN];
8 int low_cost[MAXN];
9 int pre[MAXN];
10 unsigned prime(
int n);
11 int DFS(
int i,
int sum,
int p);
12 bool mark[MAXN];
13 int main()
14 {
15 //freopen("acm.acm","r",stdin);
16 int p;
17 int edge;
18 unsigned tem;
19 int i;
20 int j;
21 int u;
22 int v;
23 while(cin>>p>>
edge)
24 {
25 memset(mark,
false,
sizeof(mark));
26 for(i =
0; i < p; ++
i)
27 {
28 for(j =
0; j < p; ++
j)
29 _m[i][j] =
inf;
30 }
31 for(i =
0; i < edge; ++
i)
32 {
33 cin>>u>>
v;
34 --
u;
35 --
v;
36 cin>>
tem;
37 if(_m[u][v] ==
inf)
38 {
39 _m[u][v] =
tem;
40 _m[u][v] *= -
1;
41 _m[v][u] =
_m[u][v];
42 }
43 else
44 if(tem > _m[u][v]*(-
1))
45 {
46 _m[u][v] =
tem;
47 _m[u][v] *= -
1;
48 _m[v][u] =
_m[u][v];
49 }
50 }
51 mark[
0] =
true;
52 tem = -
prime(p);
53 if(DFS(
0,
1,p) ==
p)
54 cout<<tem<<
endl;
55 else
56 cout<<-
1<<
endl;
57 }
58 }
59 int DFS(
int i,
int sum,
int n)
60 {
61 int j;
62 for(j =
0; j < n; ++
j)
63 {
64 if(i != j && _m[i][j] != inf && !
mark[j])
65 {
66 mark[j] =
true;
67 sum = DFS(j,sum+
1,n);
68 }
69 }
70 return sum;
71 }
72 unsigned prime(
int n)
73 {
74 int i;
75 int j;
76 int k;
77 unsigned sum =
0;
78 int min;
79 for(i =
1; i < n; ++
i)
80 {
81 low_cost[i] = _m[
0][i];
82 pre[i] =
0;
83 }
84 for(i =
1; i < n; ++
i)
85 {
86 min =
inf;
87 for(j =
1; j < n; ++
j)
88 {
89 if(low_cost[j]&&low_cost[j] <
min)
90 {
91 k =
j;
92 min =
low_cost[j];
93 }
94 }
95 sum +=
low_cost[k];
96 low_cost[k] =
0;
97 for(j =
1; j < n; ++
j)
98 {
99 if(_m[k][j] < low_cost[j] &&
low_cost[j])
100 {
101 low_cost[j] =
_m[k][j];
102 pre[j] =
k;
103 }
104 }
105 }
106 return sum;
107 }
转载于:https://www.cnblogs.com/gavinsp/p/4568376.html
相关资源：垃圾分类数据集及代码
