【BZOJ4298】[ONTAK2015]Bajtocja

左手的ㄟ右手 2022-10-03 00:37 2阅读 0赞

## 【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<bits/stdc++.h>
    #define ll long long
    #define N 5005
    #define M 1000005
    #define D 205
    #define ull unsigned long long
    
    using 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<<ans<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10558795.html