直接貼代碼了，沒什么好說(shuō)的
1 import java.io.*;
2 import java.util.Arrays;
3 class node implements Comparable
4 {
5 int a,b,c;
6 public int compareTo(Object pos)
7 {
8 return ((node)pos).c-c;
9 }
10 };
11 public class Main {
12 static int pre[];
13 static int find(int pos)
14 {
15 if(pre[pos]==pos)
16 return pos;
17 else
18 {
19 pre[pos]=find(pre[pos]);
20 return pre[pos];
21 }
22 }
23 public static void main(String[] args) throws IOException{
24 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
25 int n,m;
26 in.nextToken();
27 n=(int)in.nval;
28 in.nextToken();
29 m=(int)in.nval;
30 node []data=new node[m];
31 pre=new int[n+1];
32 for(int i=1;i<=n;i++)
33 pre[i]=i;
34 for(int i=0;i<m;i++)
35 {
36 data[i]=new node();
37 in.nextToken();
38 data[i].a=(int)in.nval;
39 in.nextToken();
40 data[i].b=(int)in.nval;
41 in.nextToken();
42 data[i].c=(int)in.nval;
43 }
44 Arrays.sort(data);
45 int count=0,total=0;
46 for(int i=0;i<m&&count<n-1;i++)
47 {
48 if(find(data[i].a)!=find(data[i].b))
49 {
50 pre[find(data[i].a)]=find(data[i].b);
51 total+=data[i].c;
52 count++;
53 }
54 }
55 if(count<n-1)
56 System.out.println(-1);
57 else
58 System.out.println(total);
59
60 }
61
62 }
63