zoj2966 build the electric system

 1 2966最小树并查集模板Build The Electric System
 2 #include<stdio.h>
 3 #include<algorithm>
 4  using namespace std;
 5 int pre[501],fee;
 6 struct side
 7 {
 8     int u,v,x;
 9 }a[501];
10 bool cmp(const side & a,const side & b)
11 {
12     return a.x<b.x;
13 }
14 int find(int x)
15 {
16     int r=x;
17     while(pre[r]!=r)r=pre[r];
18     int i=x;int j;
19     while(i!=r)
20     {
21         j=pre[i];
22         pre[i]=r;
23         i=j;
24     }
25     return r;
26 
27 }
28 void join(int x,int y,int i)
29 {
30     int fx=find(x),fy=find(y);
31     if(fx!=fy)
32     {
33         pre[fx]=fy;
34         if(i!=-1)fee+=a[i].x;
35     }
36     return;
37 }
38 int main()
39 {
40     int cas,n,e,nu,nv,nx;
41     scanf("%d",&cas);
42          while(cas--)
43     {
44         fee=0;
45        scanf("%d%d",&n,&e);
46        for(int i=0;i<n;i++)pre[i]=i;
47             int t=0;
48        for(int i=0;i<e;i++)
49        {
50            scanf("%d%d%d",&nu,&nv,&nx);
51            if(nx==0)join(nu,nv,-1);
52            else {a[t].u=nu;a[t].v=nv;a[t].x=nx;t++;} 
53        }
54        sort(a,a+t,cmp);
55        for(int i=0;i<t;i++)
56        {
57            join(a[i].u,a[i].v,i);
58        }
59        printf("%d\n",fee);
60     }
61 }