hdu 4750 Count The Pairs

本文从WordPress迁移而来, 查看全部WordPress迁移文章

并查集应用

题意:无向图,对于任意两个点u,v,从u到v有多条路径,每条路径都会有一个最长边,在这些最长边的最小值,称为f(u,v)。对于每个询问t,要统计所有满足f(u,v) >= t的点对,注意(1,2)和(2,1)被视为不同的点对。

这题数据很大,各种图论算法想想都知道是不太可行了,要从一个角度去考虑,然后证明一个性质,问题就变得清晰了。对所有边升序排序,用kruskal算法对原图构建最小生成树,当构建完毕的时候,其实可以知道,任意一对点(u,v)都是互相可达的,另外对于任意f(u,v)一定包含在里面。因为如果再往MST中加边,只不过是增加了一些点对之间的路径,但是新加入的这个边一定比之前的边都要大,不可能更新f(u,v)。所以我们在一边构建MST的时候,就能一边进行统计了。每添加一条树边之前,先统计这条边两端的集合的元素个数,分别为na,nb,那么这条边产生的点对数为 2nanb。最后将所有的树边,它的权,和它计算出来的答案,保存在一个表中。对于询问t,因为是要f(u,v) >= t,所以可以二分查找到f(u,v),然后再求和,所以一开始可以先预处理出后缀和,具体看代码中的solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010
#define M 500010
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,m,tot;
struct edge{
int u,v; LL w;
}e[M];
struct ANS{
LL w,res;
ANS(){}
ANS(LL _w , LL _res){
w = _w; res = _res;
}
}a[N];
int p[N],num[N];

bool cmp_e(edge x , edge y){
return x.w < y.w;
}

int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}

void solve(){
sort(e,e+m,cmp_e);
for(int i = 0; i < n; i++){
p[i] = i; num[i] = 1;
}
tot = 0;
for(int i = 0; i < m; i++){
int u = e[i].u;
int v = e[i].v;
LL w = e[i].w;
int rtu = find(u);
int rtv = find(v);
if(rtu == rtv) continue;
LL res = 2 * num[rtu] * num[rtv];
a[++tot] = ANS(w,res);
num[rtu] += num[rtv];
p[rtv] = rtu;
}
LL sum = 0;
for(int i = tot; i >= 1; i--){
a[i].res += sum; sum = a[i].res;
}
}

int binary(LL key){
int low = 1 , high = tot , index = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(a[mid].w >= key){
index = mid; high = mid - 1;
}
else low = mid + 1;
}
return index;
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 0; i < m; i++)
scanf("%d%d%I64d",&e[i].u,&e[i].v,&e[i].w);
solve();
int q;
scanf("%d",&q);
while(q--){
LL t;
scanf("%I64d",&t);
int index = binary(t);
printf("%I64d\n",a[index].res);
}
}
return 0;
}