1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<stdio.h>
#include<utility>
#include<algorithm>
int p[100005];
int a[1000005], b[1000005];
std::pair<int, int> S[1000005];
int par(int a){
if(p[a]==a) return a;
return par(p[a]);
}
int main(){
int n, m, t, ans;
while(1){
scanf("%d%d", &n, &m);
if(n==0&&m==0) break;
t=0;
ans=0;
for(int i=1; i<=n; i++){
p[i] = i;
}
for(int i=0; i<m; i++){
scanf("%d%d%d", &a[i], &b[i], &S[i].first);
S[i].second = i;
}
std::sort(S, S+m);
for(int i=0; i<m&&t<n-1; i++){
if(par(a[S[i].second])!=par(b[S[i].second])){
ans+=S[i].first;
p[par(b[S[i].second])] = par(a[S[i].second]);
p[b[S[i].second]] = par(a[S[i].second]);
t++;
}
}
if(t==n-1) printf("%d\n", ans);
else printf("-1\n");
}
}
|