记录

#include<bits/stdc++.h>
namespace xcy{
const int MAXN=100005;
const int MAXM=300005;
typedef long long ll;
ll dy[MAXM<<1],fa[MAXN],head[MAXN],rev[MAXN],a[MAXN],ans[2],cnt,num,n,m,i,j,k,l;
std::bitset<MAXM>vis;
struct Edge{ll to,pre,val;}ed[MAXN<<1],gd[MAXM];
struct Node{ll dfn,dep,fa,son,top,siz=1;}td[MAXN];
struct Tnode{ll l,r,max[2];}nd[MAXN<<2];
#define nowl nd[N].l
#define nowr nd[N].r
#define lch N<<1
#define rch (N<<1)+1
#define nowm nd[N].max[0]
#define lcm nd[lch].max[0]
#define rcm nd[rch].max[0]
#define nown nd[N].max[1]
#define lcn nd[lch].max[1]
#define rcn nd[rch].max[1]

inline void fread(ll &X){X=0;char C=getchar();while(!isdigit(C))C=getchar();while(isdigit(C))X=(X<<1)+(X<<3)+(C^48),C=getchar();}
inline void fout(ll X){if(!X){putchar('0'),putchar('\n');return;}char C[25]{};ll Len=0;while(X)C[++Len]=X%10+'0',X/=10;for(;Len;--Len)putchar(C[Len]);putchar('\n');}
inline void add(ll F,ll T,ll V){ed[++cnt].to=T;ed[cnt].val=V;ed[cnt].pre=head[F];head[F]=cnt;}
inline ll find(ll X){return X==fa[X]?X:fa[X]=find(fa[X]);}
inline void merge(ll A,ll B){A=find(A);B=find(B);fa[A]=B;}
void build(ll N,ll L,ll R)
{
	nowl=L;nowr=R;nown=nowm=-0x3f3f3f3f;
	if(L==R){nowm=rev[L];return;}
	ll M=L+R>>1;
	build(lch,L,M);
	build(rch,M+1,R);
	nowm=lcm;nown=lcn;
	if(rcm>nowm){nown=nowm,nowm=rcm;
		if(rcn>nown)nown=rcn;}
	else if(rcm>nown)nown=rcm;
}
#define sp std::pair<ll,ll>
sp query(ll N,ll L,ll R)
{
	if(L>R)return {-0x3f3f3f3f,-0x3f3f3f3f};
	if(L<=nowl&&nowr<=R)return {nowm,nown};
	sp P{-0x3f3f3f3f,-0x3f3f3f3f},Rp;
	ll M=nowl+nowr>>1;
	if(L<=M)P=query(lch,L,R);
	if(M<R)Rp=query(rch,L,R);
	else return P;
	if(Rp.first>P.first){P.second=P.first,P.first=Rp.first;
		if(Rp.second>P.second)P.second=Rp.second;}
	else if(Rp.first>P.second)P.second=Rp.first;
	return P;
}
void dfs(ll N,ll D)
{
	td[N].dep=D;
	for(int I=head[N];I;I=ed[I].pre)
	{
		int J=ed[I].to;
		if(td[J].dep)continue;
		a[J]=dy[I];td[J].fa=N;dfs(J,D+1);
		td[N].siz+=td[J].siz;
		if(!td[N].son||(td[J].siz>td[td[N].son].siz))td[N].son=J;
	}
}
void dfn(ll N,ll T)
{
	td[N].dfn=++num;rev[num]=a[N];td[N].top=T;
	if(td[N].son)dfn(td[N].son,T);
	for(int I=head[N];I;I=ed[I].pre)
		if(!td[ed[I].to].dfn)
			dfn(ed[I].to,ed[I].to);
}
sp tquery(ll A,ll B)
{
	sp P{-0x3f3f3f3f,-0x3f3f3f3f},Rp;
	while(td[A].top!=td[B].top)
	{
		if(td[td[A].top].dep<td[td[B].top].dep)std::swap(A,B);
		Rp=query(1,td[td[A].top].dfn,td[A].dfn);
		if(Rp.first>P.first){P.second=P.first,P.first=Rp.first;
			if(Rp.second>P.second)P.second=Rp.second;}
		else if(Rp.first>P.second)P.second=Rp.first;
		A=td[td[A].top].fa;
	}
	if(td[A].dep>td[B].dep)std::swap(A,B);
	Rp=query(1,td[td[A].son].dfn,td[B].dfn);
	if(Rp.first>P.first){P.second=P.first,P.first=Rp.first;
		if(Rp.second>P.second)P.second=Rp.second;}
	else if(Rp.first>P.second)P.second=Rp.first;
	return P;
}

int mian()
{
	fread(n),fread(m);
	for(i=1;i<=n;++i)fa[i]=i;
	for(i=1;i<=m;++i)fread(gd[i].to),fread(gd[i].pre),fread(gd[i].val);
	std::sort(gd+1,gd+m+1,[&](Edge A,Edge B){return A.val<B.val;});
	for(i=j=1;i<=m;++i)
	{
		k=gd[i].to,l=gd[i].pre,num=gd[i].val;
		if(find(k)!=find(l))ans[0]+=num,++j,merge(k,l),add(k,l,num),add(l,k,num),vis[i]=1,dy[cnt]=dy[cnt-1]=num;
		if(j==n)break;
	}num=0;ans[1]=0x3f3f3f3f3f3f3f3f;
	dfs(1,1);dfn(1,1);build(1,1,n);
	for(i=1;i<=m;++i)
	{
		if(vis[i]||gd[i].to==gd[i].pre)continue;
		sp Ans=tquery(gd[i].to,gd[i].pre);
		if(gd[i].val>Ans.first)ans[1]=std::min(ans[1],ans[0]-Ans.first+gd[i].val);
		else ans[1]=std::min(ans[1],ans[0]-Ans.second+gd[i].val);
	}
	fout(ans[1]);
	return 0;
}}
int main(){return xcy::mian();}

像自环、初始化之类的细节感觉都处理了，调了1h不知道错在哪