cdoj1215 （并查集）

从小到大排序，判断连通。
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,m,u[1000005],v[1000005],w[1000005],r[1000005],p[1005];
 6 int cmp(const int i,const int j)
 7 {
 8     return w[i]<w[j];
 9 }
10 int find (int x)
11 {
12     if(p[x]==x)
13     return x;
14     else return p[x]=find(p[x]);
15 }
16 int kruskal()
17 {
18     int ans=0;
19     for(int i=0;i<=n;i++) p[i]=i;
20     for(int i=0;i<m;i++) r[i]=i;
21     sort(r,r+m,cmp);
22     for(int i=0;i<m;i++)
23     {
24         int e=r[i];int x=find(u[e]);int y=find(v[i]);
25         if(x!=y)
26         {
27             ans+=w[e];
28             p[x]=y;
29         }
30 
31     }
32     return ans;
33 }
34 int main()
35 {
36     int T;
37     scanf("%d",&T);
38     while(T--)
39     {
40         scanf("%d%d",&n,&m);
41         for(int i=0;i<m;i++)
42         scanf("%d%d%d",&u[i],&v[i],&w[i]);
43         printf("%d
",kruskal());
44     }
45     return 0;
46 }