为什么就

#5

过不了
调一上午了
源代码：

#include <bits/stdc++.h>
using namespace std;

const int inf=2147483647;
struct edge{
	int u,v,w,i;
	friend bool operator <(edge x,edge y){
		return x.w<y.w;
	}
}st[300005];
struct ikun{
	int p,w,id;
	ikun() {};
	ikun(int P,int W,int Id){p=P;w=W;id=Id;}
};
vector<ikun> e[100005];
int n,m;
long long sum,ans=9223372036854775807;
int dep[100005];
int f[100005][18];
int g[100005][18][2];
int fa[100005];
bool vis[300005],vv[100005],flag[300005];

inline int in() {
    int x = 0, f = 1;char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void init(int u,int fu){
	dep[u]=dep[fu]+1;
	for (int i=0;i<17;i++){
		f[u][i+1]=f[f[u][i]][i];
		g[u][i+1][0]=max(g[u][i][0],g[f[u][i]][i][0]);
		if (g[u][i][0]==g[f[u][i]][i][0]) g[u][i+1][1]=g[u][i][0];//max(g[u][i][1],g[f[u][i]][i][1]);
		else if (g[u][i][0]<g[f[u][i]][i][0]) g[u][i+1][1]=max(g[u][i][0],g[f[u][i]][i][1]);
		else if (g[u][i][0]>g[f[u][i]][i][0]) g[u][i+1][1]=max(g[u][i][1],g[f[u][i]][i][0]);
	}
	for (long unsigned int i=0;i<e[u].size();i++){
		int v=e[u][i].p,ww=e[u][i].w,iid=e[u][i].id;
		if (!vis[iid]||v==fu) continue;
		f[v][0]=u;
		g[v][0][0]=ww;
		g[v][0][1]=-inf;
		init(v,u);
	}
}

pair<int,int> lca(int u,int v){
	int da=0,ca=0;
	if (dep[u]<dep[v]) u^=v^=u^=v;
	for (int i=17;i>=0;i--){
		if (dep[f[u][i]]>=dep[v]) {
			if (g[u][i][0]>da) ca=max(da,g[u][i][1]),da=g[u][i][0];
			else if (g[u][i][0]==da) ca=da;
			else ca=max(ca,g[u][i][0]);
			u=f[u][i];
		}
		if (u==v) return make_pair(da,ca);
	}
	for (int i=17;i>=0;i--){
		if (f[u][i]!=f[v][i]||i==0){
			if (g[u][i][0]==g[v][i][0]) da=max(da,g[u][i][0]),ca=max(ca,g[v][i][0]);
			else if (g[u][i][0]>g[v][i][0]){
				if (g[u][i][0]>da) da=g[u][i][0],ca=max(ca,max(g[u][i][1],max(g[v][i][0],g[v][i][1])));
				else ca=max(ca,g[u][i][0]);
			}
			else if (g[u][i][0]<g[v][i][0]){
				if (g[v][i][0]>da) da=g[v][i][0],ca=max(ca,max(g[v][i][1],max(g[u][i][0],g[u][i][1])));
				else ca=max(ca,g[v][i][0]);
			}
			if (i!=0)u=f[u][i],v=f[v][i];
		}
	}
	return make_pair(da,ca);
}

int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

int main(){
	n=in(),m=in();
	for (int i=1;i<=m;i++){
		int u,v,ww;
		u=in(),v=in(),ww=in();
		if (u==v) continue;
		e[u].push_back(ikun(v,ww,i));
		e[v].push_back(ikun(u,ww,i));
		st[i].u=u,st[i].v=v,st[i].w=ww,st[i].i=i;
	}
	sort(st+1,st+1+m);
	for (int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,j=1;i<=m&&j<n;i++) {
		int u=st[i].u,v=st[i].v;
		int fu=find(u),fv=find(v);
		if (fu!=fv) 
			j++,fa[fu]=fv,vis[st[i].i]=1,sum+=st[i].w;
	}
	
	g[1][0][1]=-inf;
	init(1,0);
	
	for (int i=1;i<=n;i++){
		for (long unsigned int j=0;j<e[i].size();j++){
			int v=e[i][j].p,ww=e[i][j].w,iid=e[i][j].id;
			if (vis[iid]) continue;
			else if (flag[iid]) continue;
			pair<int,int> pr=lca(i,v);
			int saikyo=pr.first,tsugi=pr.second;
			if (ww>saikyo) 
				{if (sum-saikyo+ww!=sum) ans=min(ans,sum-saikyo+ww),flag[iid]=1;}
			else if (ww==saikyo)
				{if (sum-tsugi+ww!=sum) ans=min(ans,sum-tsugi+ww),flag[iid]=1;}
		}
	}
	
	printf("%lld",ans);
	
	return 0;
}