本文主要是介绍2023NOIP A层联测6 万花筒,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意
有一张有 n n n个点 m m m条边的无向带权图 G G G,小艾将它放到一个万花筒中观察。在万花筒中,对于每条边 ( u , v , w ) ∈ G (u,v,w)\in G (u,v,w)∈G,会在 H H H中生成全体 ( ( u + 1 ) m o d + 1 , ( v + i ) m o d n + 1 , w ) ((u+1)\bmod+1,(v+i)\bmod n+1,w) ((u+1)mod+1,(v+i)modn+1,w)的边,最后的图 H H H就是在万花筒中看到的图。
求这个图 H H H的最小生成树的权值和,保证生成树存在。
有 T T T组数据。
1 ≤ T ≤ 100 , 1 ≤ n , w ≤ 1 0 9 , ∑ m ≤ 1 0 5 1\leq T\leq 100,1\leq n,w\leq 10^9,\sum m\leq 10^5 1≤T≤100,1≤n,w≤109,∑m≤105
题解
对于 G G G中的每一条边 ( u , v , w ) (u,v,w) (u,v,w),令 k = ( u − v + n ) % n k=(u-v+n)\% n k=(u−v+n)%n,则在 H H H中,任意两个满足 ( i − j + n ) % n = k (i-j+n)\% n=k (i−j+n)%n=k的两个点 i , j i,j i,j都有一条权值为 w w w的边。那么,对于 G G G中的每一条边 ( u , v , w ) (u,v,w) (u,v,w),我们记其对应的 H H H中的边集为 T ( k , w ) T(k,w) T(k,w)。
利用 Kruskal \text{Kruskal} Kruskal算法的思想,我们将这些边集按 w w w从小到大排序,并依次遍历以构建最小生成树。
设当前的 n n n个点中没有任何两个点有连边,当前枚举到的边集为 T ( k , w ) T(k,w) T(k,w),则将 n n n中所有满足 ( i − j + n ) % n = k (i-j+n)\% n=k (i−j+n)%n=k且不在同一个连通块的两个点 i , j i,j i,j连一条边。那么,这 n n n个点就会分为 d = gcd ( n , k ) d=\gcd(n,k) d=gcd(n,k)个连通块,且同一个连通块中的点的编号模 d d d后的值一定相等(可以自己举几个例子试一下)。
这样的话,这个图就连上了 n − d n-d n−d条边,边集 T ( k , w ) T(k,w) T(k,w)对答案的贡献为 ( n − d ) × w (n-d)\times w (n−d)×w。
再考虑下一组边集 T ( k ′ , w ′ ) T(k',w') T(k′,w′),类似地,将 n n n中所有满足 ( i − j + n ) % n = k ′ (i-j+n)\% n=k' (i−j+n)%n=k′且不在同一个连通块的两个点 i , j i,j i,j连一条边。这时,我们发现, i i i所在的连通块中的点模 d d d后的值均为 i % d i\%d i%d, j j j所在的连通块中的点模 d d d后的值均为 j % d j\% d j%d,那么我们可以将 i i i和 j j j连边看作 i % d i\% d i%d和 j % d j\% d j%d连边( i % d i\% d i%d或 j % d j\% d j%d的值为 0 0 0时将其值看作 d d d),这样显然是等价的。
换句话说,我们将每个连通块都看成了一个点,而这个点表示的连通块就是一棵树。
那么,在连完 T ( k , w ) T(k,w) T(k,w)的边之后,问题可以看作剩下 d d d个点且其中没有任何两个点有连边,要求其在连上剩下的边集后的最小生成树的权值和。
每次多加一个边集,就按上面所说的操作一次,并算上边的贡献。因为保证生成树存在,所以最终一定只剩下一个点,而这一个点所表示的连通块就是图 H H H的最小生成树。
将每次操作的贡献求和,即可得到答案。
时间复杂度为 O ( m ) O(m) O(m)。
code
#include<bits/stdc++.h>
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;
}
这篇关于2023NOIP A层联测6 万花筒的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!