记录编号	302926	评测结果	AAAAAAAAAA
题目名称	次小生成树	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.793 s
提交时间	2016-09-04 18:55:27	内存使用	147.91 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 1000010
#define maxe 3000100
#define mid ((l+r)>>1)
#define L rt<<1,l,mid
#define R rt<<1|1,mid+1,r
using namespace std;
/*
严格次小生成树
在不严格的基础上加上一个次小记录 
*/
typedef long long LL;
 
int n,m;
 
struct Edge{
	int from,to,next,w;
	bool is;
}ee[maxe],e[maxn*2];
bool cmp(const Edge&a,const Edge&b){return a.w<b.w;}
int head[maxn],tot;
void Ladd(int from,int to,int w)
{
	e[++tot].to=to;
	e[tot].w=w;
	e[tot].next=head[from];
	head[from]=tot;
}
//--------------bian----------
int be[maxn];
int Lfind(int x)
{
	int o=x,temp;
	while(o!=be[o])o=be[o];
	while(be[x]!=o){
		int temp=be[x];
		be[x]=o;
		x=temp;
	}
	return o;
}
int Ffind(int x){
	return be[x]==x?x:be[x]=Ffind(be[x]);
}
LL Lkruskal()
{
	int cnt=0;
	LL ans=0;
	sort(ee+1,ee+1+m,cmp);
	for(int i=1;i<=n;i++)be[i]=i;
	int rx,ry;
	for(int i=1;i<=m;i++){
		rx=Lfind(ee[i].from);
		ry=Lfind(ee[i].to);
		if(rx!=ry){
			be[rx]=ry;
			Ladd(ee[i].from,ee[i].to,ee[i].w);
			Ladd(ee[i].to,ee[i].from,ee[i].w);
			ans+=(LL)ee[i].w;
			ee[i].is=true;
			cnt++;
			if(cnt==n-1) return ans;
		}
	}
}
//---------mst---------
int size[maxn],son[maxn],fa[maxn],deep[maxn];
int top[maxn],dfn[maxn],pos[maxn],val[maxn],dfn_cnt;
void Ldfs1(int x)
{
	size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(size[to])continue;
		fa[to]=x;deep[to]=deep[x]+1;
		val[to]=e[i].w;
		Ldfs1(to);
		size[x]+=size[to];
		if(size[to]>size[son[x]])son[x]=to;
	}
}
void Ldfs2(int x,int t)
{
	dfn[x]=++dfn_cnt;
	pos[dfn_cnt]=x;
	top[x]=t;
	if(son[x])Ldfs2(son[x],t);
	for(int i=head[x];i;i=e[i].next){
		int to=e[i].to;
		if(!top[to])Ldfs2(to,to);
	}
}
//-----------shu pou de dfs------------
int t_max[maxn*4],t_sec[maxn*4];
void Lbuild(int rt,int l,int r){
	if(l==r){
		t_max[rt]=val[pos[l]];
		t_sec[rt]=-0x7f7f7f7f;
		return;
	}
	Lbuild(L);Lbuild(R);
	t_max[rt]=max(t_max[rt<<1],t_max[rt<<1|1]);
	if(t_max[rt<<1]<t_max[rt<<1|1]) 
		t_sec[rt]=max(t_max[rt<<1],t_sec[rt<<1|1]);
	if(t_max[rt<<1]>t_max[rt<<1|1]) 
		t_sec[rt]=max(t_max[rt<<1|1],t_sec[rt<<1]);
	if(t_max[rt<<1]==t_max[rt<<1|1]) 
		t_sec[rt]=max(t_sec[rt<<1],t_sec[rt<<1|1]);
}

int Ltree_max(int rt,int l,int r,int s,int t,int v)
{
	if(s<=l&&t>=r){
		if(t_max[rt]==v) return t_sec[rt];
		return t_max[rt];
	}
	if(t<=mid)return Ltree_max(L,s,t,v);
	if(s>mid) return Ltree_max(R,s,t,v);
	return max(Ltree_max(L,s,t,v),Ltree_max(R,s,t,v));
}
int Lquery(int x,int y,int v)
{
	int ans=0;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		ans=max(ans,Ltree_max(1,1,n,dfn[top[x]],dfn[x],v));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	if(x!=y) ans=max(ans,Ltree_max(1,1,n,dfn[x]+1,dfn[y],v));
	return ans;
}
//-------------segment tree+ shu pou------------
int main()
{
	freopen("secmst.in","r",stdin);freopen("secmst.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&ee[i].from,&ee[i].to,&ee[i].w);
	
	LL ans1 = Lkruskal(),ans2=0x7f7f7f7f;
	deep[1]=1;
	Ldfs1(1);
	Ldfs2(1,1);
	Lbuild(1,1,n);
	for(int i=1;i<=m;i++){
		if(ee[i].is)continue;
		LL x=ee[i].w-Lquery(ee[i].from,ee[i].to,ee[i].w);
		ans2=min(ans2,x);
	}
	printf("%lld",ans1+ans2);
	//getchar();getchar();
	fclose(stdin);
	fclose(stdout);
	return 0;
}