度杂复间时

哈希 并查集

题面

给出$D$张图,每张图上有$n$个点。每一次（总共$m$次）连接某一张图的两个点,询问在所有图中都连通的有序点对数量。

• $10pts$ $D=1,n\leq5000,m\leq10^6$
• $60pts$ $D\leq100,n\leq300,m\leq300$
• $100pts$ $D\leq200,n\leq5000,m\leq10^6$

解析

$10pts$算法

只有一张图？联通？
显然并查集。
每次我们连两个点，就相当于让两个联通块联通。
他们联通起来，会产生两者大小之积×2个新联通有序点对。
复杂度$O(nlogn)$（如果胆小把并查集算作$O(logn)$的话）

fp(i,1,m)
    {
      re int x=gi(),y=gi(),k=gi(),fx=find(k,x),fy=find(k,y);
      if(fx^fy) f[k][fx]=fy,ans+=sz[k][fx]*sz[k][fy]*2,sz[k][fy]+=sz[k][fx];
      wri(ans);putchar('\n');
    }

$60pts$算法

两个点怎样才能被统计进答案?总共被有效联通$D$次（应该存在本来联通却还加边的）。
在此用$vis[i][j]$统计有效联通次数。
现有$D$个图，则维护$D$个并查集。
受到$10pts$算法的启发，每次联通两个点时，将两个联通块的点一一对应（复杂度$O(n^2)$)，一一增加有效联通次数。如果有两点次数达到$D$次，即可统计进答案。
其实还是暴力
总复杂度最坏为$O(mn^2)$,实际估计为$O(mlog^2n)$，数据水可以$AC$。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5100;
int f[250][N],vis[N][N],d,m,n,ans,sz[250][N],sta1[N],sta2[N],tp1,tp2;
il int find(re int k,re int x)
{
  return (x==f[k][x]?x:f[k][x]=find(k,f[k][x]));
}
int main()
{
  freopen("iriya.in","r",stdin);
  freopen("iriya.out","w",stdout);
  d=gi();ans=n=gi();m=gi();
  fp(i,1,d) fp(j,1,n) f[i][j]=j,sz[i][j]=1;
  if(d==1)
    fp(i,1,m)
    {
      re int x=gi(),y=gi(),k=gi(),fx=find(k,x),fy=find(k,y);
      if(fx^fy) f[k][fx]=fy,ans+=sz[k][fx]*sz[k][fy]*2,sz[k][fy]+=sz[k][fx];
      wri(ans);putchar('\n');
    }
  else 
    while(m--)
    {
      re int x=gi(),y=gi(),k=gi(),fx=find(k,x),fy=find(k,y);
      if(fx^fy)
    {
      tp1=tp2=0;
      fp(i,1,n)
        {
          re int ff=find(k,i);
          if(ff==fx) sta1[++tp1]=i;
          if(ff==fy) sta2[++tp2]=i;
        }
      f[k][fx]=fy;
      fp(i,1,tp1)
        fp(j,1,tp2)
        {
          ++vis[sta1[i]][sta2[j]];++vis[sta2[j]][sta1[i]];
              if(vis[sta1[i]][sta2[j]]>=d) ans+=2;
        }
    }
      wri(ans);putchar('\n');
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

$100pts$算法

以上算法都是暴力算法，并且无法延伸到正解。
所以我们换一个角度来思考。
两个点被统计进答案，当且仅当所有图上两点属于同一联通块。
正常判断需要$O(Dlogn)$。
如此从正解方向上想的暴力复杂度为$O(mDlogn)$，也有$60pts$。
但是，判断时的复杂度可以优化。
如果我们将$D$张图上$i$节点所属联通块编号拼成一个字符串，我们就可以$O(1)$字符串哈希比较两个点是否所有图上所属联通块编号都相同了。