「bzoj4298」「ONTAK2015」Bajtocja - Hash+启发式合并+链表 | Bill Yang's Blog

「bzoj4298」「ONTAK2015」Bajtocja - Hash+启发式合并+链表

题目大意

    给定$d$张无向图,每张图都有$n$个点。一开始,在任何一张图中都没有任何边。接下来有$m$次操作,每次操作会给出$a,b,k$,意为在第$k$张图中的点$a$和点$b$之间添加一条无向边。你需要在每次操作之后输出有序数对$(a,b)$的个数,使得$1\le a,b\le n$,且$a$点和$b$点在$d$张图中都连通。


题目分析

神奇的Hash降维技巧。
在每张图中,我们给每个点一个连通块标号,属于同一个连通块的点标号相同。第$i$张图第$j$个点标号为$f[i,j]$。
现在我们将不同图的相同点的标号$f[j,i]$串起来,Hash一下得到$Hash[i]$。
若两个点Hash相同,说明它们在$d$张图中均连通。

添加新的边时需要将两个连通块合并,利用启发式合并的技巧,将小连通块合并到大连通块,修改所有小连通块的标号以及Hash值。

现在考虑统计答案。
设某个连通块大小为$s$,每次给连通块增加一个点时需要$+2s+1$,每次给连通块删一个点时需要$-2(s-1)-1$。
那么问题来了,我怎么知道相同连通块的信息呢?
问得好,再Hash一遍,每个相同的Hash值统计大小即可。

据说map<>很慢,那我们用list<>吧。


代码

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxd=205,maxn=5005,maxs=262143,Base=10007;
struct node {
LL v;
int num;
node(LL v=0,int num=0):v(v),num(num) {}
};
list<node> L[maxs+1];
vector<int> edges[maxd][maxn];
LL Hash[maxn],Pow[maxd],f[maxd][maxn],size[maxd][maxn];
int ans=0;
void ins(LL v) {
int pos=v&maxs;
for(auto &x:L[pos])if(x.v==v) {ans+=x.num*2+1;x.num++;return;}
ans++,L[pos].push_back(node(v,1));
}
void del(LL v) {
int pos=v&maxs;
for(auto it=L[pos].begin(); it!=L[pos].end(); it++) {
auto &x=*it;
if(x.v!=v)continue;
ans-=(x.num-1)*2+1;
if(--x.num==0)L[pos].erase(it);
return;
}
}
void Dfs(int z,int x,int fa,int id) {
del(Hash[x]),Hash[x]-=Pow[z]*f[z][x];
f[z][x]=id;
Hash[x]+=Pow[z]*id,ins(Hash[x]);
for(int y:edges[z][x])if(y!=fa)Dfs(z,y,x,id);
}
void merge(int z,int x,int y) {
if(f[z][x]==f[z][y])return;
if(size[z][f[z][x]]>size[z][f[z][y]])swap(x,y);
size[z][f[z][y]]+=size[z][f[z][x]];
edges[z][x].push_back(y),edges[z][y].push_back(x);
Dfs(z,x,y,f[z][y]);
}
int d,n,m;
int main() {
d=Get_Int();
n=Get_Int();
m=Get_Int();
Pow[0]=1;
for(int i=1; i<d; i++)Pow[i]=Pow[i-1]*Base;
for(int i=1; i<=n; ins(Hash[i++]))
for(int j=0; j<d; j++)f[j][i]=i,size[j][i]=1,Hash[i]+=Pow[j]*i;
while(m--) {
int x=Get_Int(),y=Get_Int(),z=Get_Int();
merge(--z,x,y);
printf("%d\n",ans);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%