【题解】BZOJ 4298 [ONTAK2015]Bajtocja

请注意,本文编写于 101 天前,最后修改于 101 天前,其中某些信息可能已经过时。

Problem

给定 $d$ 张无向图,各有 $n$ 个点,编号 $1-n$,开始时没有任何的边

接下有 $m$ 次操作,每次使得第 $k$ 张图中编号为 $a,b$ 的两个点联通

求每次操作后满足在 $d$ 张图中 $a,b$ 均联通的点对数

Thougtht

点的联通性问题当然是用并查集啦
在 $d$ 张图中均联通即 $\forall i, find(x,i)=find(y,i)$

那么如果令 $g(x)=\sum_{i=1}^{d} find(x,i)*n^{i-1}$
那么只需要查询有多少个数满足 $g(a)=g(b)$

丢到哈希表里面即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 5010;
map <int, int> mp;
int ans;
int d, n, m;
int col[N];
struct Graph {
    int siz[N], bel[N];
    int col[N];
    vector <int> son[N];
    void reset() {
        for(int i = 1; i <= n; ++ i) {
            bel[i] = i; son[i].push_back(i);
            col[i] = rand() % (1 << 30);
            :: col[i] ^= col[i];
        }
    }
    void merge(int a, int b) {
        int fa = bel[a], fb = bel[b];
        if(fa == fb) return;
        if(son[fa].size() > son[fb].size()) swap(fa, fb);
        for(auto it : son[fa]) {
            -- mp[:: col[it]];
            ans -= mp[:: col[it]];
            :: col[it] ^= (col[it] ^ col[fb]);
            ans += mp[:: col[it]];
            ++ mp[:: col[it]];

            bel[it] = fb;
            col[it] = col[fb];
        }
        for(auto it : son[fa])
            son[fb].push_back(it);
        son[fa].clear();
    }
}G[210];
int main() {
    srand(time(NULL));
    d = read(); n = read(); m = read();
    for(int i = 1; i <= d; ++ i)
        G[i].reset();
    for(int i = 1; i <= n; ++ i)
        ++ mp[col[i]];
    for(int i = 1; i <= m; ++ i) {
        int a = read(), b = read(), k = read();
        G[k].merge(a, b);
        printf("%d\n", ans * 2 + n);
    }
    return 0;
}
Comments

添加新评论