思路：
典型的最小生成树，Prim搞定。但是速度好慢，用堆应该好一点。
#include <stdio.h>
int N, M;
struct node 
{
int idx, w;
struct node *next;
};
struct node edges[40032], *map[1024], *exists[1024][1024];
int edges_cnt;
char visited[1024];
__inline void add(int a, int b, int w)
{
struct node *p;
if (exists[a][b]) {
if (exists[a][b]->w < w)
exists[a][b]->w = w;
return ;
}
p = &edges[edges_cnt++];
p->idx = b;
p->w = w;
p->next = map[a];
map[a] = p;
exists[a][b] = p;
}
int main()
{
int i, j, k, max_val, max_idx, sum;
struct node *p;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d%d%d", &i, &j, &k);
add(i, j, k);
add(j, i, k);
}
visited[1] = 1;
sum = 0;
for (k = 0; k < N - 1; k++) {
max_val = -1;
for (i = 1; i <= N; i++) {
if (!visited[i])
continue;
for (p = map[i]; p; p = p->next)
if (!visited[p->idx] && p->w > max_val) {
max_val = p->w;
max_idx = p->idx;
}
}
if (max_val == -1)
break;
sum += max_val;
visited[max_idx] = 1;
}
printf("%d\n", k == N - 1 ? sum : -1);
return 0;
}