[nowcoder5669J]Jumping on the Graph

考虑枚举$k$并求出$f(k)=\sum_{i=1}^{n}\limits\sum_{j=i+1}^{n}\limits [D(i,j)\le k]$，那么答案就是$\sum_{i=1}^{1e9}(f(i)-f(i-1))\cdot i$

考虑如何求出$a_{k}$：将大于$k$的边标成1，小于等于$k$的边标成0，令$L(i,j)$表示新图中两点间的最短路，那么$D(i,j)\le k$当且仅当$L(i,j)\le 1$

可以有这样一个算法，从小到大枚举$k$，并将边权为0的边所构成的连通块缩点，记连通块大小分别为$a_{1},a_{2},...,a_{n'}$，两个连通块之间的边集合为$E$（删去重边自环），那么答案为$\sum_{i=1}^{n'}c(a_{i},2)+\sum_{(i,j)\in E}a_{i}\cdot a_{j}$

考虑维护$k$变大所带来的影响，即将一条边权为1的边改为0：设这条边相连的两个连通块为$x$和$y$（$x\ne y$），则有变化量$且\Delta=a_{y}\sum_{(i,x)\in E}a_{i}+a_{x}\sum_{(i,y)\in E}a_{i}-(a_{x}+a_{y})\sum_{(i,x)\in E且(i,y)\in E}a_{i}$，由于每一条初始的边最多对应新图中的一条边，因此仍然可以暴力存储每一个点的出边并启发式合并，然后对$x$和$y$的连通块大小分类讨论：

1.$a_{x},a_{y}\le \sqrt{M}$或$\sqrt{M}\le a_{x},a_{y}$，暴力枚举即可（第二类最多只出现$\sqrt{M}$次）

2.$a_{x}\le \sqrt{M}\le a_{y}$（交换同理），那么对于$\sqrt{M}\le a_{y}$需要预处理出$s_{y}=\sum_{i=1}^{n}[(i,y)\in E]\cdot a_{i}$（要预处理的$s$最多$\sqrt{M}$个），并用$set$维护出边集合来支持查找

复杂度分析，包括预处理和计算：预处理，包括出边的$set$和$\sqrt{M}$个点的$s$，$s$的修改可以暴力枚举每一个点是否要修改，复杂度为$o(M\sqrt{M}+M\log^{2}M)$；计算，1为$o(M\sqrt{M})$，2为$o(M\log M)$（由于每一个数最多作为$a_{x}$参与一次），总复杂度即为$o(M\sqrt{M}+M\log^{2}M)$

具体实现细节较多，可能会有很多地方需要修改，详见代码

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 struct ji{

 5     int x,y,z;

 6 }e[N<<1];

 7 vector<int>v;

 8 set<int>s[N];

 9 set<int>::iterator it;

10 int K,n,m,sz[N],f[N],tot[N];

11 long long ans;

12 bool cmp(ji x,ji y){

13     return x.z<y.z;

14 }

15 int find(int k){

16     if (k==f[k])return k;

17     return f[k]=find(f[k]);

18 }

19 int calc(int k){

20     if (tot[k])return tot[k];

21     int ans=0;

22     for(it=s[k].begin();it!=s[k].end();it++)ans+=sz[(*it)];

23     return ans;

24 }

25 int main(){

26     scanf("%d%d",&n,&m);

27     for(int i=1;i<=m;i++){

28         scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);

29         if (e[i].x!=e[i].y){

30             s[e[i].x].insert(e[i].y);

31             s[e[i].y].insert(e[i].x);

32         }

33     }

34     sort(e+1,e+m+1,cmp);

35     K=400;

36     for(int i=1;i<=n;i++){

37         f[i]=i;

38         sz[i]=1;

39     }

40     for(int i=1;i<=n;i++)

41         if (s[i].size()>K){

42             tot[i]=calc(i);

43             v.push_back(i);

44         }

45     for(int i=1;i<=m;i++){

46         int x=find(e[i].x),y=find(e[i].y);

47         if (x==y)continue;

48         if ((tot[x])&&(!tot[y]))swap(x,y);

49         long long sum=1LL*sz[x]*(calc(y)-sz[x]);

50         for(it=s[x].begin();it!=s[x].end();it++){

51             s[(*it)].erase(x);

52             if ((*it)==y)continue;

53             sum+=1LL*sz[y]*sz[(*it)];

54             if (tot[(*it)])tot[(*it)]-=sz[x];

55             if (s[y].find((*it))!=s[y].end())sum-=1LL*(sz[x]+sz[y])*sz[(*it)];

56             else{

57                 s[y].insert((*it));

58                 if (tot[y])tot[y]+=sz[(*it)];

59                 s[(*it)].insert(y);

60                 if (tot[(*it)])tot[(*it)]+=sz[y];

61             }

62         }

63         if (tot[y])tot[y]-=sz[x];

64         if ((!tot[y])&&(s[y].size()>K)){

65             tot[y]=calc(y);

66             v.push_back(y);

67         }

68         f[x]=y;

69         sz[y]+=sz[x];

70         ans+=sum*e[i].z;

71         if (tot[x])

72             for(int j=0;j<v.size();j++)

73                 if (v[j]==x){

74                     for(int k=j;k;k--)swap(v[k],v[k-1]);

75                     v.erase(v.begin());

76                     break;

77                 }

78         s[x].clear();

79         for(int j=0;j<v.size();j++)

80             if ((v[j]!=y)&&(s[y].find(v[j])!=s[y].end()))tot[v[j]]+=sz[x];

81         sz[x]=0;

82     }

83     printf("%lld",ans);

84 }

巴特西

[nowcoder5669J]Jumping on the Graph

最新文章

热门文章