2023NOIP A层联测6 万花筒

题目大意

有一张有$n$个点$m$条边的无向带权图$G$，小艾将它放到一个万花筒中观察。在万花筒中，对于每条边$(u,v,w)\in G$，会在$H$中生成全体$((u+1)\mathrm{mod}+1,(v+i)\mathrm{mod}n+1,w)$的边，最后的图$H$就是在万花筒中看到的图。

求这个图$H$的最小生成树的权值和，保证生成树存在。

有$T$组数据。

$1\le T\le 100,1\le n,w\le 10^9,\sum m\le 10^5$

题解

对于$G$中的每一条边$(u,v,w)$，令$k=(u-v+n)\%n$，则在$H$中，任意两个满足$(i-j+n)\%n=k$的两个点$i,j$都有一条权值为$w$的边。那么，对于$G$中的每一条边$(u,v,w)$，我们记其对应的$H$中的边集为$T(k,w)$。

利用$\text{Kruskal}$算法的思想，我们将这些边集按$w$从小到大排序，并依次遍历以构建最小生成树。

设当前的$n$个点中没有任何两个点有连边，当前枚举到的边集为$T(k,w)$，则将$n$中所有满足$(i-j+n)\%n=k$且不在同一个连通块的两个点$i,j$连一条边。那么，这$n$个点就会分为$d=\gcd (n,k)$个连通块，且同一个连通块中的点的编号模$d$后的值一定相等（可以自己举几个例子试一下）。

这样的话，这个图就连上了$n-d$条边，边集$T(k,w)$对答案的贡献为$(n-d)\times w$。

再考虑下一组边集$T(k^{\prime },w^{\prime })$，类似地，将$n$中所有满足$(i-j+n)\%n=k^{\prime }$且不在同一个连通块的两个点$i,j$连一条边。这时，我们发现，$i$所在的连通块中的点模$d$后的值均为$i\%d$，$j$所在的连通块中的点模$d$后的值均为$j\%d$，那么我们可以将$i$和$j$连边看作$i\%d$和$j\%d$连边（$i\%d$或$j\%d$的值为$0$时将其值看作$d$），这样显然是等价的。

换句话说，我们将每个连通块都看成了一个点，而这个点表示的连通块就是一棵树。

那么，在连完$T(k,w)$的边之后，问题可以看作剩下$d$个点且其中没有任何两个点有连边，要求其在连上剩下的边集后的最小生成树的权值和。

每次多加一个边集，就按上面所说的操作一次，并算上边的贡献。因为保证生成树存在，所以最终一定只剩下一个点，而这一个点所表示的连通块就是图$H$的最小生成树。

将每次操作的贡献求和，即可得到答案。

时间复杂度为$O(m)$。

code

#include
using namespace std;
int T,n,m,now,d;
long long ans;
struct node{
	int t,w;
}v[100005];
bool cmp(node ax,node bx){
	return ax.w<bx.w;
}
int gcd(int i,int j){
	while(j){
		i%=j;swap(i,j);
	}
	return i;
}
int main()
{
	freopen("kaleidoscope.in","r",stdin);
	freopen("kaleidoscope.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1,x,y,z;i<=m;i++){
			scanf("%d%d%d",&x,&y,&z);
			v[i].t=(x-y+n)%n;
			v[i].w=z;
		}
		sort(v+1,v+m+1,cmp);
		now=n;
		ans=0;
		for(int i=1;i<=m;i++){
			d=gcd(now,v[i].t%now);
			ans+=1ll*(now-d)*v[i].w;
			now=d;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40