HDU 5441 Travel（并查集+统计节点个数）

http://acm.hdu.edu.cn/showproblem.php?pid=5441

题意：
给出一个图，每条边有一个距离，现在有多个询问，每个询问有一个距离值d，对于每一个询问，计算出有多少点对（x，y）使得在x到y的路径上没有一条边的距离大于d。

思路：
只要边距离小于d，那就是可行的，直接加入并查集来维护。并查集需要维护一下树的节点个数。

将边和询问都排序离线处理。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 int n,m,k;
 9 int p[20005], num[20005];
10 ll ans[5005];
11 
12 
13 struct node
14 {
15     int u,v,w;
16     bool operator< (const node& rhs) const
17     {
18         return w<rhs.w;
19     }
20 }e[100005];
21 
22 struct Node
23 {
24     int id;
25     int val;
26     bool operator< (const Node& rhs) const
27     {
28         return val<rhs.val;
29     }
30 }query[5005];
31 
32 
33 int finds(int x)
34 {
35     return x==p[x]?x:p[x] = finds(p[x]);
36 }
37 
38 int main()
39 {
40     //freopen("in.txt","r",stdin);
41     int T;
42     scanf("%d",&T);
43     while(T--)
44     {
45         scanf("%d%d%d",&n,&m,&k);
46         for(int i=1;i<=n;i++)  {p[i] = i; num[i] = 1;}
47         for(int i=1;i<=m;i++)
48             scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
49         sort(e+1,e+m+1);
50         for(int i=1;i<=k;i++)
51         {
52             scanf("%d",&query[i].val);
53             query[i].id = i;
54         }
55         sort(query+1,query+k+1);
56         query[0].id = 0;
57         ll tmp = 0;
58         int pos = 1;
59         ans[0] = 0;
60         for(int i=1;i<=m && pos<=k;i++)
61         {
62             while(e[i].w>query[pos].val && pos<=k)
63             {
64                 ans[query[pos].id] = ans[query[pos-1].id];
65                 pos++;
66             }
67             while(e[i].w<=query[pos].val && i<=m)
68             {
69                 int x = finds(e[i].u);
70                 int y = finds(e[i].v);
71                 if(x!=y)
72                 {
73                     p[x] = y;
74                     tmp = tmp-num[y]*(num[y]-1)-num[x]*(num[x]-1);
75                     num[y] += num[x];
76                     tmp = tmp+num[y]*(num[y]-1);
77                 }
78                 i++;
79             }
80             ans[query[pos].id] = tmp;
81             pos++;
82             i--;
83         }
84         while(pos<=k)
85         {
86             ans[query[pos].id] = ans[query[pos-1].id];
87             pos++;
88         }
89         for(int i=1;i<=k;i++)  printf("%lld
",ans[i]);
90     }
91     return 0;
92 }