hdu5441Travel【并查集】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const long long maxn = 1000005;
 8 struct E {
 9     long long u, v, w;
10 }e[maxn];
11 bool cmp(E e1, E e2) {
12     if(e1.w != e2.w) {
13         return e1.w < e2.w;
14     }
15     return e1.u < e2.u;
16 }
17 struct ANS {
18     long long id;
19     long long num;
20 }ans[maxn];
21 bool cmp2(ANS a1, ANS a2) {
22     if(a1.num != a2.num) {
23         return a1.num < a2.num;
24     }
25     return a1.id < a2.id;
26 }
27 
28 long long fa[maxn];
29 long long xx[maxn];
30 long long find(long long x) {
31     if(x == fa[x]) {
32         return x;
33     }
34     return fa[x] = find(fa[x]);
35 }
36 void init(long long n) {
37     for(long long i = 0; i <= n; i++) {
38         fa[i] = i;
39         xx[i] = 1;
40     }
41 }
42 void unin(long long x, long long y) {
43     long long fx = find(x), fy = find(y);
44     if(fx != fy) {
45         fa[fx] = fy;
46         xx[fy] += xx[fx];
47         xx[fx] = 0;
48     }
49 }
50 
51 long long val[maxn];
52 
53 int main() {
54     long long t, n, m, q;
55     scanf("%I64d",&t);
56     while(t--) {
57         scanf("%I64d%I64d%I64d",&n, &m, &q);
58         memset(xx, 0, sizeof(xx));
59         init(n);
60         for(long long i = 0; i < m; i++) {
61             scanf("%I64d%I64d%I64d",&e[i].u, &e[i].v, &e[i].w);
62         }
63         sort(e, e + m, cmp);
64         for(long long i = 0; i < q; i++) {
65             scanf("%I64d",&ans[i].num);
66             ans[i].id = i;
67         }
68         sort(ans, ans + q, cmp2);
69         long long i = 0, j = 0;
70         long long _ans = 0;
71         while(i < m && j < q) {
72             while(i < m && j < q && e[i].w <= ans[j].num) {
73                 long long x = find(e[i].u), y = find(e[i].v);
74                 if(x != y) {
75                     _ans += xx[x] * xx[y];
76                     unin(x, y);
77                 }
78                 i++;
79             }
80             val[ans[j++].id] = _ans;
81         }
82         while(j < q) {
83             val[ans[j++].id] = _ans;
84         }
85         for(long long i = 0; i < q; i++) {
86             printf("%I64d
", val[i] * 2);
87         }
88     }
89 }