记录编号	384576	评测结果	RRRRRRRRRR
题目名称	[USACO Open05] 疾病管理	最终得分	0
用户昵称	hee	是否通过	未通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-03-18 18:08:28	内存使用	38.65 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#define MAXX 100000
using namespace std;
struct E{
  int from,to,w;
}e[MAXX*6+1];
struct Edge{
  int nxt,to,w;
}edge[2*MAXX-1];
int head[MAXX],sig;
int f[MAXX][24],fa[MAXX],deep[MAXX],maxx[MAXX][24],maxs[MAXX][24];
int n,m,tot,x,y,z,ans;
bool in[MAXX*6+1];
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
void insert(int r1,int r2){int ri=find(r1),rii=find(r2);fa[ri]=rii;}
void add(int ff,int tt,int qq){edge[++tot].nxt=head[ff];edge[tot].to=tt;head[ff]=tot;edge[tot].w=qq;}
bool comp(const E & a,const E & b){return a.w<b.w;}
void dfs(int num,int faa){
  for(int i=head[num];i;i=edge[i].nxt)if(edge[i].to!=faa){
      int to=edge[i].to;deep[to]=deep[num]+1,maxx[to][0]=edge[i].w,maxs[to][0]=-1,f[to][0]=num,dfs(to,num);
  }
}
void update1(int &a,int &b,int x,int y,int xx,int yy){
  if(x==xx){b=max(yy,y);a=xx;return;}
  if(x>xx)swap(x,xx),swap(y,yy);a=xx,b=max(x,yy);
}
void update2(int x,int i,int & nowx,int & nows){
  if(nowx==maxx[x][i])nows=max(nows,maxs[x][i]);
  else if(nowx>maxx[x][i])nows=max(nows,maxx[x][i]);
  else{
    nowx=maxx[x][i];
    nows=max(nows,maxs[x][i]);
  }
}
int update3(int nowx,int nows,int w){
  if(nowx==w)return w-nows;
  return w-nowx;
}
int LCA(int x,int y,int w){
  if(deep[y]>deep[x])swap(x,y);
  int dee=deep[x]-deep[y],nowx=-1,nows=-1;
  for(int i=0;(1<<i)<=dee;i++)if(dee&(1<<i)){
      update2(x,i,nowx,nows),x=f[x][i];
    }
  if(x==y)return update3(nowx,nows,w);
  for(int i=int(floor(log(n)/log(2)));i>=0;--i)if(f[x][i]!=f[y][i])
  update2(y,i,nowx,nows),update2(x,i,nowx,nows),x=f[x][i],y=f[y][i];
  x=f[x][0],y=f[y][0];
  return update3(nowx,nows,w);
}
void dododo(){
  maxs[1][0]=-1,maxs[0][0]=-1;
  deep[1]=1,dfs(1,0);
   for(int i=1;i<=n;++i)
  for(int j=1;(1<<j)<=n;++j)
   {
     f[i][j]=f[f[i][j-1]][j-1];
    if(f[i][j]!=0)
      update1(maxx[i][j],maxs[i][j],maxx[i][j-1],maxs[i][j-1],maxx[f[i][j-1]][j-1],maxs[f[i][j-1]][j-1]);
  }
}
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",&e[i].from,&e[i].to,&e[i].w);
  for(int i=1;i<=n;++i)fa[i]=i;
  sort(e+1,e+m+1,comp);
  for(int i=1;i<=n;++i)if(find(e[i].from)!=find(e[i].to)){
      int ff=e[i].from,tt=e[i].to;
      insert(ff,tt),ans+=e[i].w,add(ff,tt,e[i].w),add(tt,ff,e[i].w),sig++,in[i]=true;
      if(sig==n-1)break;
    }dododo();
  int deta=0x7fffffff;
  for(int i=1;i<=m;++i)if(!in[i])deta=min(deta,LCA(e[i].from,e[i].to,e[i].w));
  printf("%d",deta+ans-1);
  return 0;
}