记录编号	459423	评测结果	AAAAAAAAAA
题目名称	次小生成树	最终得分	100
用户昵称	YPZ_979	是否通过	通过
代码语言	C++	运行时间	0.261 s
提交时间	2017-10-13 09:02:40	内存使用	26.25 MiB

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int maxn=100001;
struct node{
    int to,net;
    ll w;
}eg[maxn*6],opp[maxn*6];
struct Edge{
    int x,y;
    ll w;
}e[maxn*3];
int head[maxn],nume;
int head2[maxn],nume2;
int fa[maxn],pd[maxn],IS[maxn],n,m;
ll val[maxn];
int dfn[maxn],Index;
ll sum,ans=1e17;
int comp(const Edge &a,const Edge &b){
    return a.w<b.w;
}
bool ok;
int find(int x) {
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void Union(int x,int y) {
    fa[x]=y;
}
void add(int x,int y,ll w) {
    eg[++nume].to=y;eg[nume].w=w;eg[nume].net=head[x];head[x]=nume;
}
void add2(int x,int y,ll w) {
    opp[++nume2].to=y;opp[nume2].w=w;opp[nume2].net=head2[x];head2[x]=nume2;
}
 
void Kruskal() {
    sort(e+1,e+m+1,comp);int i;
    for(i=1;i<=n;i++) fa[i]=i;
    int k=0;
    for(i=1;i<=m;i++) {
	int r1=find(e[i].x),r2=find(e[i].y);
	if(r1!=r2){
	    Union(r1,r2);
	    k++;
	    sum+=e[i].w;
	    add(e[i].x,e[i].y,e[i].w);
	    add(e[i].y,e[i].x,e[i].w);
	     IS[i]=1;
	    if(k==n-1) break;
	}
    }
}
 
void dfs(int x,int fu) {
    dfn[x]=++Index;
    for(int i=head[x];i;i=eg[i].net) {
	int to=eg[i].to;
	if(to==fu)continue;	
	if(!dfn[to]) {
	    dfs(to,x); 
	}
    }
}
 
void dfs2(int x,int fu) { 
    for(int i=head[x];i;i=eg[i].net) {
	int to=eg[i].to;
	if(to==fu)continue;
	if(dfn[to]<dfn[x]) continue;
	dfs2(to,x);
	val[x]=min(val[x],val[to]);
    }
}
 
int main() {
    freopen("secmst.in","r",stdin);
    freopen("secmst.out","w",stdout);
    scanf("%d%d",&n,&m);int i;
    for(i=1;i<=m;i++) {
	scanf("%d%d%lld",&e[i].x,&e[i].y,&e[i].w);
    }
    Kruskal();
    for(i=1;i<=m;i++) if(!IS[i]) add2(e[i].x,e[i].y,e[i].w),add2(e[i].y,e[i].x,e[i].w);
    dfs(1,0);
    for(i=1;i<=n;i++) val[i]=1e17;
    for(int x=1;x<=n;x++){
	for(i=head2[x];i;i=opp[i].net) {
	    val[x]=min(val[x],opp[i].w);
	}
    }
    dfs2(1,0);
    for(i=1;i<=m;i++){
	if(!IS[i]) continue;
        ll kkk=sum;
	kkk-=e[i].w;	
        if(dfn[e[i].x]<dfn[e[i].y]) kkk+=val[e[i].y];
	else kkk+=val[e[i].x];
	if(kkk<=sum) continue;
	ans=min(kkk,ans);
    }    
    cout<<ans;
    return 0;
}