【BZOJ4298】[ONTAK2015]Bajtocja

【BZOJ4298】[ONTAK2015]Bajtocja

Description

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

Input

第一行包含三个正整数d,n,m(1<=d<=200，1<=n<=5000，1<=m<=1000000)，依次表示图的个数，点的个数和操作的个数。
接下来m行，每行包含三个正整数a,b,k(1<=a,b<=n，1<=k<=d)，依次描述每一个操作。

Output

输出m行m个正整数，依次表示每次操作之后满足条件的有序数对(a,b)的个数。

Sample Input

3 4 10
1 2 1
2 1 2
1 2 3
3 4 1
1 3 2
2 3 3
2 4 2
3 4 3
3 4 2
1 3 1

Sample Output

4
4
6
6
6
6
6
8
8
16

神仙题啊。
考虑给每个图开一个并查集。设\(f_{i,k}\)表示第\(i\)个点在第\(k\)张图中并查集的根。然后我们对于每个点\(i\)，我们将\(d\)张图中的\(f_i\)当成一个字符串并算出\(hash\)值。如果两个点\(i,j\)的\(hash\)值相同，则他们在每一张图中都连通。

具体操作可以开一个\(hash\)表。然后并查集启发式合并。还要用\(unsigned\ long\ long\)。

代码：

#include
#define ll long long
#define N 5005
#define M 1000005
#define D 205
#define ull unsigned long longusing namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int d,n,m;
struct road {int to,next;};
ll ans;
const int mod=10000007;
const ull p=2337;
ull pw[D];
ull g[N];
struct Hash {int h[mod],cnt;int size[N*N/5],nxt[N*N/5];ull val[N*N/5];void Insert(ull x) {int v=x%mod;for(int i=h[v];i;i=nxt[i]) {if(val[i]==x) {size[i]++;ans+=2*size[i]-1;return ;}}val[++cnt]=x;nxt[cnt]=h[v];size[cnt]=1;h[v]=cnt;ans++;}void Del(ull x) {int v=x%mod;for(int i=h[v];i;i=nxt[i]) {if(val[i]==x) {ans-=2*size[i]-1;size[i]--;return ;}}}
}ha;struct BCJ {int id;int f[N],size[N];void Init() {for(int i=1;i<=n;i++) f[i]=i,size[i]=1;}int Getf(int v) {return v==f[v]?v:f[v]=Getf(f[v]);}road s[N<<1];int h[N],cnt;void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}void dfs(int v,int fa) {ha.Del(g[v]);g[v]-=f[v]*pw[id-1];f[v]=fa;g[v]+=f[v]*pw[id-1];ha.Insert(g[v]);for(int i=h[v];i;i=s[i].next) {int to=s[i].to;dfs(to,fa);}}void Merge(int a,int b) {a=Getf(a),b=Getf(b);if(a==b) return ;if(size[a]>size[b]) swap(a,b);add(b,a);size[b]+=size[a];dfs(a,b);}
}T[D];int main() {d=Get(),n=Get(),m=Get();for(int i=1;i<=d;i++) T[i].Init();pw[0]=1;for(int i=1;i<=d;i++) pw[i]=pw[i-1]*p;for(int i=1;i<=d;i++) T[i].id=i;for(int i=1;i<=n;i++) {for(int j=1;j<=d;j++) g[i]=g[i]*p+i;ha.Insert(g[i]);}int x,y,z;for(int i=1;i<=m;i++) {x=Get(),y=Get(),z=Get();T[z].Merge(x,y);cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！