【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<
     
      <<"\n";    }    return 0;}