记录编号	347118	评测结果	WWWWWWWWWW
题目名称	次小生成树	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	1.913 s
提交时间	2016-11-12 20:37:25	内存使用	47.23 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long i64;
const int maxn=100010,maxe=300010;
struct edge{
	int from,to;
	i64 w;
	bool used;
	bool operator<(const edge &e)const{return w<e.w;}
}e[maxe];
i64 Kruskal();
int findroot(int);
void mergeset(int,int);
void dfs(int);
void init();
void query(int,int);
int n,m,k,prt[maxn],depth[maxn],f[maxn][20];
i64 g[maxn][20],h[maxn][20],tmp,ans,mxa,mxb;
vector<int>G[maxn];
vector<i64>W[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout);
#endif
	memset(g,-62,sizeof(g));
	memset(h,-62,sizeof(h));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%lld",&e[i].from,&e[i].to,&e[i].w);
	tmp=Kruskal();
	ans=~(1ll<<63);
	for(int i=1;i<=m;i++)if(!e[i].used){
		query(e[i].from,e[i].to);
		if(e[i].w==mxa)ans=min(ans,tmp+e[i].w-mxb);
		else ans=min(ans,tmp+e[i].w-mxa);
	}
	printf("%lld",ans);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
i64 Kruskal(){
	i64 ans=0ll;
	for(int i=1;i<=n;i++)prt[i]=i;
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++)if(findroot(e[i].from)!=findroot(e[i].to)){
		e[i].used=true;
		ans+=e[i].w;
		G[e[i].from].push_back(e[i].to);
		W[e[i].from].push_back(e[i].w);
		G[e[i].to].push_back(e[i].from);
		W[e[i].to].push_back(e[i].w);
		mergeset(e[i].from,e[i].to);
	}
	return ans;
}
int findroot(int x){return prt[x]==x?x:(prt[x]=findroot(prt[x]));}
void mergeset(int x,int y){prt[findroot(x)]=findroot(y);}
void dfs(int x){
	int cnt=G[x].size();
	for(int i=0;i<cnt;i++)if(G[x][i]!=f[x][0]){
		f[G[x][i]][0]=x;
		depth[G[x][i]]=depth[x]+1;
		g[G[x][i]][0]=W[x][i];
		dfs(G[x][i]);
	}
}
void init(){
	for(int j=1;j<=k;j++)for(int i=1;i<=n;i++){
		f[i][j]=f[f[i][j-1]][j-1];
		if(g[i][j-1]>g[f[i][j-1]][j-1]){
			g[i][j]=g[i][j-1];
			h[i][j]=max(g[f[i][j-1]][j-1],max(h[i][j-1],h[f[i][j-1]][j-1]));
		}
		else if(g[i][j-1]<g[f[i][j-1]][j-1]){
			g[i][j]=g[f[i][j-1]][j-1];
			h[i][j]=max(g[i][j-1],max(h[i][j-1],h[f[i][j-1]][j-1]));
		}
		else{
			g[i][j]=g[i][j-1];
			h[i][j]=max(h[i][j-1],h[f[i][j-1]][j-1]);
		}
	}
}
void query(int x,int y){
	mxa=mxb=1ll<<63;
	if(depth[x]<depth[y])swap(x,y);
	for(int j=k;j!=-1;j--)if(depth[f[x][j]]>=depth[f[y][j]]){
		if(mxa<g[x][j]){
			mxb=max(mxa,h[x][j]);
			mxa=g[x][j];
		}
		else if(mxa>g[x][j])mxb=max(mxb,g[x][j]);
		else mxb=max(mxb,h[x][j]);
		x=f[x][j];
	}
	if(x==y)return;
	for(int j=k;j!=-1;j--)if(f[x][j]!=f[y][j]){
		if(mxa<g[x][j]){
			mxb=max(mxa,h[x][j]);
			mxa=g[x][j];
		}
		else if(mxa>g[x][j])mxb=max(mxb,g[x][j]);
		else mxb=max(mxb,h[x][j]);
		if(mxa<g[y][j]){
			mxb=max(mxa,h[y][j]);
			mxa=g[y][j];
		}
		else if(mxa>g[y][j])mxb=max(mxb,g[y][j]);
		else mxb=max(mxb,h[y][j]);
		x=f[x][j];
		y=f[y][j];
	}
	if(mxa<g[x][0]){
		mxb=max(mxa,h[x][0]);
		mxa=g[x][0];
	}
	else if(mxa>g[x][0])mxb=max(mxb,g[x][0]);
	else mxb=max(mxb,h[x][0]);
	if(mxa<g[y][0]){
		mxb=max(mxa,h[y][0]);
		mxa=g[y][0];
	}
	else if(mxa>g[y][0])mxb=max(mxb,g[y][0]);
	else mxb=max(mxb,h[y][0]);
}