RT.

评测记录

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long LL;

struct vw
{
	LL v,w;
};

struct xyz
{
	LL x,y,z;
}a[300010];

LL n,m;
vector<vw> edge[100010];
LL fa[100010];
LL f[100010][30];
LL maxn[100010][30];
LL max2[100010][30];
LL dep[100010];
LL tmp=0;
LL ans=1e18;

void init()
{
	for(LL i=1;i<=n;i++)
	{
		fa[i]=i;
	}
}

LL find(LL x)
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}

void link(LL x,LL y)
{
	fa[find(x)]=find(y);
}

bool cmp(xyz x,xyz y)
{
	return x.z<y.z;
}

void dfs(LL p,LL father)
{
	f[p][0]=father;
	dep[p]=dep[father]+1;
	for(LL i=1;i<=20;i++)
	{
		f[p][i]=f[f[p][i-1]][i-1];
		maxn[p][i]=max(maxn[p][i-1],maxn[f[p][i-1]][i-1]);
		max2[p][i]=max(max2[p][i-1],max2[f[p][i-1]][i-1]);
		if(maxn[p][i-1]!=maxn[f[p][i-1]][i-1])
		{
			max2[p][i]=max(max2[p][i],min(maxn[p][i-1],maxn[f[p][i-1]][i-1]));
		}
	}
	for(LL i=0;i<edge[p].size();i++)
	{
		LL v=edge[p][i].v;
		LL w=edge[p][i].w;
		if(v==father)
		{
			continue;
		}
		max2[v][0]=-1e18;
		maxn[v][0]=w;
		dfs(v,p);
	}
}

pair<LL,LL> lca(LL a,LL b)
{
	if(dep[a]<dep[b])
	{
		swap(a,b);
	}
	LL ans1=-1e18;
	LL ans2=-1e18;
	for(LL i=20;i>=0;i--)
	{
		if(dep[f[a][i]]>=dep[b])
		{
			ans1=max(ans1,maxn[a][i]);
			ans2=max(ans2,max2[a][i]);
			a=f[a][i];
		}
	}
	if(a==b)
	{
		return {ans1,ans2};
	}
	for(LL i=20;i>=0;i--)
	{
		if(f[a][i]!=f[b][i])
		{
			ans1=max(ans1,max(maxn[a][i],maxn[b][i]));
			ans2=max(ans2,max(max2[a][i],max2[b][i]));
			a=f[a][i];
			b=f[b][i];
		}
	}
	return {max(ans1,max(maxn[a][0],maxn[b][0])),max(ans2,max(max2[a][0],max2[b][0]))};
}

int main()
{
	cin>>n>>m;
	init();
	for(LL i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+m+1,cmp);
	for(LL i=1;i<=m;i++)
	{
		LL x=a[i].x;
		LL y=a[i].y;
		LL z=a[i].z;
		if(find(x)!=find(y))
		{
			tmp+=z;
			link(x,y);
			edge[x].push_back({y,z});
			edge[y].push_back({x,z});
		}
	}
	dfs(1,0);
	for(LL i=1;i<=m;i++)
	{
		LL x=a[i].x;
		LL y=a[i].y;
		LL z=a[i].z;
		auto ztmp=lca(x,y);
		if(z==ztmp.first)
		{
			ans=min(ans,tmp-ztmp.second+z);
		}
		else
		{
			ans=min(ans,tmp-ztmp.first+z);
		}
	}
	cout<<ans;
	return 0;
}