记录编号	341907	评测结果	AAAAAAAAAA
题目名称	次小生成树	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	2.026 s
提交时间	2016-11-07 22:06:49	内存使用	34.59 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
#define MAXM 300010
#define MAXN 100010
#define LL long long
#define INF 1000000000000000LL
using namespace std;
struct node
{
	int U,V,VAL;
}E[MAXM],E1[MAXM];
struct NODE
{
	int begin,end,value,next;
}edge[MAXM*2];
int cnt,Head[MAXN],n,m,father[MAXN],M,P[MAXN][18],mx1[MAXN][18],mx2[MAXN][18],deep[MAXN];
bool vv[MAXM],vis[MAXN];
void addedge(int bb,int ee,int vv)
{
	edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee,int vv)
{
	addedge(bb,ee,vv);addedge(ee,bb,vv);
}
int findfather(int k)
{
	if(father[k]==k)return father[k];
	else return father[k]=findfather(father[k]);
}
int ak(int aa,int bb)
{
	int a1=findfather(aa);
	int b1=findfather(bb);
	if(a1!=b1){father[a1]=b1;return 1;}
	return 0;
}
bool cmp(node aa,node bb){return aa.VAL<bb.VAL;}
LL Kruskal()
{
	int i,tot=0,pd;
	LL sum=0LL;
	for(i=1;i<=n;i++)father[i]=i;
	for(i=1;i<=m;i++)
	{
		pd=ak(E[i].U,E[i].V);
		if(pd==1)
		{
			E1[++M]=E[i];sum+=E[i].VAL;vv[i]=true;
			tot++;if(tot==n-1)break;
		}
	}
	return sum;
}
void dfs(int u)
{
	int i,v;
	vis[u]=true;
	for(i=Head[u];i!=-1;i=edge[i].next)
	{
		v=edge[i].end;
		if(vis[v]==false)
		{
			P[v][0]=u;
			mx1[v][0]=edge[i].value;
			deep[v]=deep[u]+1;
			dfs(v);
		}
	}
}
void Ycl()
{
	int i,j,k,v1,v2;
	for(j=1;(1<<j)<=n;j++)
	{
		for(i=1;i<=n;i++)
		{
			if(P[i][j-1]!=-1)
			{
				P[i][j]=P[P[i][j-1]][j-1];
				v1=mx1[i][j-1];v2=mx1[P[i][j-1]][j-1];
				mx1[i][j]=max(v1,v2);
				mx2[i][j]=max(mx2[i][j-1],mx2[P[i][j-1]][j-1]);
				if(v1!=v2)mx2[i][j]=max(mx2[i][j],min(v1,v2));
			}
		}
	}
}
int LCA(int x,int y)
{
	int i,j;
	if(deep[x]<deep[y])swap(x,y);
	for(i=0;(1<<i)<=deep[x];i++);i--;
	for(j=i;j>=0;j--)if(deep[x]-(1<<j)>=deep[y])x=P[x][j];
	if(x==y)return x;
	for(j=i;j>=0;j--)
	{
		if(P[x][j]!=-1&&P[x][j]!=P[y][j])
		{
			x=P[x][j];
			y=P[y][j];
		}
	}
	return P[x][0];
}
int main()
{
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout);
	int i,MX1,MX2,x,y,lca,j;
	LL MST,CMST;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&E[i].U,&E[i].V,&E[i].VAL);
	}
	sort(E+1,E+m+1,cmp);
	M=0;
	MST=Kruskal();
	memset(Head,-1,sizeof(Head));cnt=1;
	for(i=1;i<=M;i++)addedge1(E1[i].U,E1[i].V,E1[i].VAL);
	memset(P,-1,sizeof(P));
	memset(mx1,-1,sizeof(mx1));
	memset(mx2,-1,sizeof(mx2));
	dfs(1);Ycl();
	CMST=INF;
	for(i=1;i<=m;i++)
	{
		if(vv[i]==false)
		{
			MX1=-1;MX2=-1;
			x=E[i].U;y=E[i].V;
			lca=LCA(x,y);
			for(j=16;j>=0;j--)
			{
				if(deep[x]-(1<<j)>=deep[lca])
				{
					if(mx1[x][j]>MX1){MX2=MX1;MX1=mx1[x][j];}
					else if(mx1[x][j]>MX2){MX2=mx1[x][j];}
					if(mx2[x][j]>MX1){MX2=MX1;MX1=mx2[x][j];}
					else if(mx2[x][j]>MX2){MX2=mx2[x][j];}
					x=P[x][j];
				}
			}
			for(j=16;j>=0;j--)
			{
				if(deep[y]-(1<<j)>=deep[lca])
				{
					if(mx1[y][j]>MX1){MX2=MX1;MX1=mx1[y][j];}
					else if(mx1[y][j]>MX2){MX2=mx1[y][j];}
					if(mx2[y][j]>MX1){MX2=MX1;MX1=mx2[y][j];}
					else if(mx2[y][j]>MX2){MX2=mx2[y][j];}
					y=P[y][j];
				}
			}
			if(E[i].VAL!=(LL)MX1)
			{
				if(MST+(LL)E[i].VAL-(LL)MX1>MST&&MST+(LL)E[i].VAL-(LL)MX1<CMST)CMST=MST+(LL)E[i].VAL-(LL)MX1;
			}
			if(E[i].VAL!=(LL)MX2)
			{
				if(MST+(LL)E[i].VAL-(LL)MX2>MST&&MST+(LL)E[i].VAL-(LL)MX2<CMST)CMST=MST+(LL)E[i].VAL-(LL)MX2;
			}
		}
	}
	printf("%lld",CMST);
	fclose(stdin);
	fclose(stdout);
}