Submission #6306780

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
#define int long long
using namespace std;
/* 
对kruskal算法的彻底理解。

A_i,B_i连接了C_i。

所以A_{i+1},B_i连接了C_i +1 等价于和这个连通块连接了C_i +1的边
（C_i<C_i +1) 所以此刻如果要连接这条边，A_i，B_i已经连接上了（必然）

所以等价于A_i A_{i+1} 连接了C_i +1,B_i B_{i+1} 连接了 C_i +2

设D数组表示 i 向后每一个点扩展连边，最小值为多少。
前缀最小值即可。做两遍。
D[i]=min(D[i],D[(i-1+n)%n]+2); 
D[i]=min(D[i],D[(i-1+n)%n]+2); 
*/
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
struct edge{
	int from,to,dis;
}g[10000001];
int F[2200001],tot,n,m;
int find(int u){
	if (F[u]!=u) F[u]=find(F[u]);
	return F[u];
}
inline void made(int a,int b,int c){
	g[++tot].from=a;g[tot].to=b;g[tot].dis=c;
}
inline bool cmp(edge a,edge b){
	return a.dis<b.dis;
}
int D[1000001];
signed main(){
	n=read();m=read();
	memset(D,0x3f,sizeof D);
	for (int i=1;i<=m;i++){
		int a=read(),b=read(),c=read();
		made(a,b,c);
		D[a]=min(D[a],c+1);
		D[b]=min(D[b],c+2);
	}
	for (int i=0;i<n;i++) F[i]=i;
	for (int i=0;i<n;i++) D[i]=min(D[i],D[(i-1+n)%n]+2);
	for (int i=0;i<n;i++) D[i]=min(D[i],D[(i-1+n)%n]+2);
	for (int i=0;i<n;i++){
		made(i,(i+1)%n,D[i]);
	}
	sort(g+1,g+1+tot,cmp);
	int ans=0;
	for (int i=1;i<=tot;i++){
		int u=g[i].from,v=g[i].to;
		int uu=find(u),vv=find(v);
		if (F[uu]!=vv){
			F[uu]=vv;ans+=g[i].dis;
		}
	}
	cout<<ans;
    return 0;
}

Submission Info

Judge Result