P4180 [BJWC2010] 严格次小生成树

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;long long q=2000000000000000000;long long sum=0;
namespace kt{
	struct edge{
		int x,y,z;
		bool operator < (const edge &x)const{
			return z<x.z;
		}
	}e[600001],other[600001],to[600001];
	int h[600001];
	int Cnt;
	void add(int x,int y,int z)
	{
		to[++Cnt]=(edge){h[x],y,z};
		h[x]=Cnt;
	}
	int sdf;
	
	int fa[600001];
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	
	int dep[600001];
	int f  [600001][22];
	int mx [600001][22];
	int mc [600001][22];
	int cmax(int a,int b,int c,int d)
	{
		int es[4]={a,b,c,d};
		sort(es,es+4);
		int asdf=unique(es,es+4)-es-1;
		if(asdf==1)return -1;//不存在 
		else return es[asdf-1];
	}
	void dfs(int x,int fa)
	{
		dep[x]=dep[fa]+1; 
		for(int i=1; i<=20; i++)
		{
			f[x][i]=f[f[x][i-1]][i-1];
			mx[x][i]=max(mx[x][i-1],mx[f[x][i-1]][i-1]);
			mc[x][i]=cmax(mx[x][i-1],mx[f[x][i-1]][i-1],mc[x][i-1],mc[f[x][i-1]][i-1]);
		}
		for(int i=h[x]; i; i=to[i].x)
		{
			int y=to[i].y;
			if(y==fa)continue;
			f[y][0]=x;
			mx[y][0]=to[i].z;
			mc[y][0]=-1;
			dfs(y,x);
		}
	}
	void lca(int x,int y,int z)
	{
		int maxn,maxnc;
		maxn=maxnc=-1;
		if(x==y)return;
		if(dep[x]<dep[y])swap(x,y);
		for(int i=20; i>=0; i--)
		{
			if(dep[f[x][i]]>=dep[y]){
				maxn=max(maxn,mx[x][i]);
				maxnc=cmax(maxnc,maxn,mx[x][i],mc[x][i]);
				x=f[x][i];
			}
		}
		if(x==y)
		{
			if(maxn<z)q=min(q,sum+z-maxn);
			else if(maxnc!=-1)q=min(q,sum+z-maxnc);
			return;
		}
		for(int i=20; i>=0; i--)
		{
			if(f[x][i]==f[y][i])continue;
			maxn=max(maxn,mx[x][i]);maxnc=cmax(maxn,maxnc,mx[x][i],mc[x][i]);
			maxn=max(maxn,mx[y][i]);maxnc=cmax(maxn,maxnc,mx[y][i],mc[y][i]);
			x=f[x][i],y=f[y][i];
		}
		maxn=max(maxn,mx[x][0]);
		maxnc=cmax(maxnc,mx[x][0],mc[x][0],maxn);
		maxn=max(maxn,mx[y][0]);
		maxnc=cmax(maxnc,mx[y][0],mc[y][0],maxn);
		if(maxn<z)q=min(q,sum+z-maxn);
		else if(maxnc!=-1)q=min(q,sum+z-maxnc);
	}
	
	void work()
	{
		sort(e+1,e+m+1);
		for(int i=1; i<=n; i++)
		{
			fa[i]=i;
		}
		for(int i=1; i<=m; i++)
		{
			int x=e[i].x,y=e[i].y,z=e[i].z;
			int fx=find(x),fy=find(y);
			if(fx!=fy){
				fa[fx]=fy;
				sum+=z;
				add(x,y,z);
				add(y,x,z);
			}
			else
				other[++sdf]=e[i];
		}
		mx[1][0]=-1;
		mc[1][0]=-1;
		dfs(1,0);
		for(int i=1;i<=sdf;i++)
		lca(other[i].x,other[i].y,other[i].z);
		cout<<q<<endl;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		kt::e[i]={x,y,z};
	}
	kt::work();
}