hdu 5441 Travel 离线操作+并查集

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5441

题意：给出一张图，有n个点，m条带权边，每次询问给出一个值val，要求删除权值>val的所有边。然后每次询问求多少个点对相连，ab和ba算成两个点对。

思路：

把每条边的权值按照从小到大排序，把每个询问记录下来，按照从小到大排序。

初始图没有边。然后按照询问加入边。对于每个询问，除了已经加入的边，再加入权值比它小的边。

然后用并查集求得每次加一条边后新产生的点对。

用一个数组cnt[i]，来记录i这个联通块的点的数量。

所以对于一条边u->v。

如果find[pre[uu]] != find[pre[vv]].

pre[uu] = vv; //连接

ans += cnt[uu]*cnt[vv]*2; //连接两个联通块后新产生的点对数量。

cnt[vv] += cnt[uu] //然后更新联通块的点数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T, n, m, q;
 4 int pre[20010];
 5 int cnt[20010];
 6 struct Edge
 7 {
 8     int u, v, w;
 9     Edge(int uu, int vv, int ww)
10     {
11         u = uu; v = vv; w = ww;
12     }
13     Edge(){}
14 }edge[100010];
15 struct Query
16 {
17     int id, qu;
18 }query[5050];
19 bool cmp(Edge e1, Edge e2)
20 {
21     return e1.w < e2.w;
22 }
23 bool cmp2(Query q1, Query q2)
24 {
25     return q1.qu < q2.qu;
26 }
27 int find(int x)
28 {
29     if(x == pre[x]) return x;
30     return pre[x] = find(pre[x]);
31 }
32 int ans[5050];
33 int main()
34 {
35     scanf("%d", &T);
36     while(T--)
37     {
38         scanf("%d%d%d", &n, &m, &q);
39         for(int i = 1; i <= m; i++)
40         {
41             scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
42         }
43         for(int i = 1; i <= q; i++)
44         {
45             scanf("%d", &query[i].qu);
46             query[i].id = i;
47         }
48         sort(edge+1, edge+1+m, cmp);
49         sort(query+1, query+1+q, cmp2);
50 
51         for(int i = 1; i <= n; i++) pre[i] = i;
52         for(int i = 1; i <= n; i++) cnt[i] = 1;
53 
54         int pos = 1;
55         int res = 0;
56         int j;
57         for(int i = 1; i <= q; i++)
58         {
59             for(j = pos; j <= m; j++)
60             {
61                 if(edge[j].w > query[i].qu)
62                 {
63                     pos = j; break;
64                 }
65                 else
66                 {
67                     int uu = find(pre[edge[j].u]);
68                     int vv = find(pre[edge[j].v]);
69                     if(uu != vv)
70                     {
71                         pre[uu] = vv;
72                         res += 2*cnt[uu]*cnt[vv];
73                         cnt[vv] += cnt[uu];
74                     }
75                 }
76             }
77             pos = j;
78             ans[query[i].id] = res;
79         }
80         for(int i = 1; i <= q; i++)
81         {
82             printf("%d
", ans[i]);
83         }
84 
85 
86     }
87     return 0;
88 }