Conscriptionpoj3723（最大生成树）

1 #include
2 #include <string.h>
3 #include
4 #include
5 using namespace std;
6 typedef struct abcd
7 {
8 int x,y,z;
9 } abcd;
10 bool cmp(abcd x,abcd y)
11 {
12 return x.z>y.z;
13 }
14 abcd a[70000];
15 int p[100000];
16 int findset(int x)
17 {
18 int i,px=x;
19 while(px!=p[px])px=p[px];
20 while(x!=px)
21 {
22 i=p[x];
23 p[x]=px;
24 x=i;
25 }
26 return px;
27 }
28 int main()
29 {
30 int t,n,m,r,i,j,x,y,z;
31 cin>>t;
32 while(t--)
33 {
34 scanf("%d%d%d",&n,&m,&r);
35 for(i=0; ii;
36 for(i=0; i)
37 {
38 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
39 a[i].y+=n;
40 }
41 sort(a,a+r,cmp);
42 long long sum=10000*(m+n);
43 for(i=0; i)
44 {
45 int x1=findset(a[i].x),y1=findset(a[i].y);
46 if(x1!=y1)
47 {
48 sum-=a[i].z;
49 p[x1]=y1;
50 }
51 }
52 cout<endl;
53 }
54 }