HDU 5441 Travel 并查集

题意：一张无向图，q个查询，对于每个x，有多少对点之间的路径中最长的一条路不大于x。

思路：比赛时王秋平写的，我补下题。这题也比较简单，将边排序，从小到大加到并查集，对查询也排序，从小到大对于每个查询把不大于x的边加到并查集，用cnt[y]记录以y为根的连通块有多少节点，那么在连通块发生变化时，ans=2 * cnt[x] * cnt[y]

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define MAXN 20005
18 #define MAXM 100005
19 #define MAXP 5005
20 using namespace std;
21 struct Edge{
22     int from, to, dist;
23     Edge(int from = 0, int to = 0, int dist = 0) :from(from), to(to), dist(dist)  {};
24 }edges[MAXM];
25 int father[MAXN], cnt[MAXN], res[MAXP];
26 struct Node{
27     int  x, pos;
28     Node(int x = 0, int pos = 0) :x(x), pos(pos){};
29 };
30 Node a[MAXP];
31 bool compare(Edge a, Edge b){
32     return  a.dist < b.dist;
33 }
34 bool comp(Node a, Node b){
35     return a.x < b.x;
36 }
37 int find(int x){
38     if (father[x] == x){
39         return x;
40     }
41     father[x] = find(father[x]);
42     return father[x];
43 }
44 int main()
45 {
46 #ifndef ONLINE_JUDGE
47     freopen("in.txt", "r", stdin);
48     //freopen("out.txt", "w", stdout);
49 #endif // OPEN_FILE
50     int T;
51     scanf("%d", &T);
52     int n, m, q;
53     while (T--){
54         scanf("%d%d%d", &n, &m, &q);
55         int x, y, z;
56         for (int i = 1; i <= m; i++){
57             scanf("%d%d%d", &x, &y, &z);
58             edges[i] = Edge(x, y, z);
59         }
60         sort(edges + 1, edges + m + 1, compare);
61         for (int i = 1; i <= q; i++){
62             scanf("%d", &a[i].x);
63             a[i].pos = i;
64         }
65         sort(a + 1, a + q + 1, comp);
66         for (int i = 1; i <= n; i++){
67             father[i] = i;
68             cnt[i] = 1;
69         }
70         int s = 1;
71         int ans = 0;
72         memset(res, 0, sizeof(res));
73         for (int i = 1; i <= q; i++){
74             for (int j = s; j <= m && edges[j].dist <= a[i].x; j++, s = j){
75                 int x = find(edges[j].from);
76                 int y = find(edges[j].to);
77                 if (x == y) continue;
78                 father[x] = y;
79                 ans += 2 * cnt[x] * cnt[y];
80                 cnt[y] += cnt[x];
81             }
82             res[a[i].pos] = ans;
83         }
84         for (int i = 1; i <= q; i++){
85             printf("%d\n", res[i]);
86         }
87     }
88 }

HDU 5441 Travel 并查集

推荐阅读