72pts求调

72pts

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,maxn=1e5+10,maxm=3e5+10;
struct edge{
	int x,y,z,f;
}w[maxm];
struct node{
	int to,nxt,w;
}e[maxm];
int f[maxn][22],max1[maxn][22],dep[maxn],g[maxn][22];//max1:最大边，g:次大边 
int fa[maxn],h[maxn],idx,minn=INF;
int n,m;
inline int read(){
	int s=0,t=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')t*=-1;
		c=getchar();
	}
	while(isdigit(c)){
		s=(s<<3)+(s<<1)+c-48;
		c=getchar();
	}
	return s*t;
}
long long ans;
bool cmp(edge a,edge b){
	return a.z<b.z;
}
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void add(int a,int b,int c){
	e[++idx].to=b;
	e[idx].nxt=h[a];
	e[idx].w=c;
	h[a]=idx;
}
void kruscal(){
	int q=1;
	sort(w,w+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int e1=find(w[i].x),e2=find(w[i].y);
		if(e1!=e2){
			ans+=w[i].z;
			w[i].f=1;
			q++;
			fa[e1]=e2;
			add(w[i].x,w[i].y,w[i].z);
			add(w[i].y,w[i].x,w[i].z);
		}
		if(q==n) break;
	}
}
void dfs(int x){
	for(int i=h[x];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==f[x][0]) continue;
		f[v][0]=x;
		max1[v][0]=e[i].w;
		dep[v]=dep[x]+1;
		for(int j=1;j<=20;j++){
			if(dep[v]<(1<<j)) break;
			f[v][j]=f[f[v][j-1]][j-1];
			max1[v][j]=max(max1[v][j-1],max1[f[v][j-1]][j-1]);
			if(max1[v][j]==max1[f[v][j-1]][j-1]){
				g[v][j]=max(g[v][j-1],g[f[v][j-1]][j-1]); 
			}
			else{
				g[v][j]=min(max1[v][j-1],max1[f[v][j-1]][j-1]);
				g[v][j]=max(g[v][j],g[f[v][j-1]][j-1]);
				g[v][j]=max(g[v][j-1],g[v][j]);
			}
 		}
		dfs(v);
	}
}
int LCA(int u,int x){
	if(dep[u]<dep[x]) swap(u,x);
	for(int i=20;i>=0;i--){
		if(dep[f[u][i]]>=dep[x]) u=f[u][i];
	}
	if(x==u) return x;
	for(int i=20;i>=0;i--){
		if(f[x][i]!=f[u][i]) x=f[x][i],u=f[u][i];
	}
	return f[x][0];
}
void change(int x,int lca,int v){
	int maxx1=0,maxx2=0;
	int d=dep[x]-dep[lca];
	for(int i=0;i<=20;i++){
		if(d<(1<<i)) break;
		if(d&(1<<i)){
			if(max1[x][i]>maxx1){
				maxx2=max(maxx1,g[x][i]);
				maxx1=max1[x][i];
			}
			x=f[x][i];
		}
	}
	if(v!=maxx1) minn=min(minn,v-maxx1);
	else minn=min(minn,v-maxx2);
}
int main(){
	n=read(),m=read();
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		w[i].x=read();w[i].y=read();w[i].z=read();
	}
	kruscal();
	dfs(1);
	for(int i=1;i<=m;i++){
		if(!w[i].f){
			int e1=w[i].x,e2=w[i].y;
			int lca=LCA(e1,e2);
			change(e1,lca,w[i].z);
			change(e2,lca,w[i].z);
		}
	}
	printf("%lld\n",ans+minn);
	return 0;
}