代码如下

显示 No valid executable file was produced by the compiler /

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long
#define IL inline
const LL N = 3e6+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
LL n,m,fa[N],tot,head[N],to[N],ne[N],id,w[N],B[N],dep[N],st[N][30],maxi[N][30],mini[N][30];
struct node
{
	LL u,v,w;
}a[N];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
LL find(LL x)
{
	return (fa[x]==x ? x : fa[x]=find(fa[x]));
}
void add(LL x,LL y,LL z)
{
	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
}

void dfs(LL id,LL fa)
{
	st[id][0]=fa;
	dep[id]=dep[fa]+1;
	for(LL i = 1;(1<<i)<=dep[id];i++)
		st[id][i]=st[st[id][i-1]][i-1];
	for(LL i = head[id];i;i=ne[i])
	{
		if(to[i]==fa) continue;
		maxi[to[i]][0]=w[i];
		mini[to[i]][0]=-INF;
		dfs(to[i],id);
	}
}
void calc()
{
	for(LL i = 1;i<=20;i++)
		for(LL j = 1;j<=n;j++)
		{
			maxi[j][i]=max(maxi[j][i-1],maxi[st[j][i-1]][i-1]);
			mini[j][i]=max(mini[j][i-1],mini[st[j][i-1]][i-1]);
			if(maxi[j][i-1]>maxi[st[j][i-1]][i-1])
				mini[j][i]=max(mini[j][i],maxi[st[j][i-1]][i-1]);
			else if(maxi[j][i-1]<maxi[st[j][i-1]][i-1])
				mini[j][i]=max(mini[j][i],maxi[j][i-1]);
		}
}
IL LL lca(LL u,LL v)
{
	if(dep[u]>dep[v])
		swap(u,v);
	for(int i = 20;i>=0;i--)
	{
		if(dep[u]<=dep[st[u][i]]) v=st[v][i];
		if(u==v) return u;
	}
	for(int i = 20;i>=0;i--)
	 	if(st[u][i]!=st[v][i])
	 		u=st[u][i],v=st[v][i];
	return st[u][0];
		 			
}
IL LL qmax(LL u,LL v,LL addin)
{
	LL ans = -INF;
	for(int i = 20;i>=0;i--)
	{
		if(dep[st[u][i]]>=dep[v])
		{
			if(addin!=maxi[u][i]) ans=max(ans,maxi[u][i]);
			else ans = max(ans,mini[u][i]);
			u=st[u][i];
		}
	}
	return ans;
}
IL LL read()
{
	char ch = getchar();
	LL f = 1,num=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
	return f*num;
}
int main()
{
	n=read(),m=read();
	for(LL i = 1;i<=n;i++) fa[i]=i;
	for(LL i = 1;i<=m;i++)
		a[i].u=read(),a[i].v=read(),a[i].w=read();
	sort(a+1,a+m+1,cmp);
	LL sum = 0;
	for(LL i = 1;i<=m;i++)
	{
		LL x = find(a[i].u),y=find(a[i].v);
		if(x!=y)
		{
			fa[x]=y;
			sum++,tot+=a[i].w;
			add(a[i].u,a[i].v,a[i].w);
			add(a[i].v,a[i].u,a[i].w);
			B[i]=1;
			if(sum==n-1) break;
		}
	}
	mini[1][0]=-INF;
	dfs(1,0);
	calc();
	LL ans = -INF;
	for(LL i =1;i<=m;i++)
	{
		if(!B[i])
		{
			LL k = lca(a[i].u,a[i].v);
			ans=max(ans,tot-max(qmax(a[i].u,k,a[i].w),qmax(a[i].v,k,a[i].w))+a[i].w);
		}
	}
	printf("%lld",ans);
} ```