#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define Maxn 300010
#define maxn 300005
using namespace std;
#define ll long long
struct edge{
int to,w,nxt;
}edge[Maxn];
int head[Maxn/
3],tot;
void addedge(
int a,
int b,
int c){
edge[tot].to=
b;
edge[tot].w=
c;
edge[tot].nxt=
head[a];
head[a]=tot++
;
}
struct line{
int u,v,w;
bool operator<(
const line &a)
const{
return w<
a.w;
}
}q[Maxn];
int vis[Maxn];
int fa[Maxn/
3];
int findset(
int x){
return fa[x]==x?x:(fa[x]=
findset(fa[x]));
}
int unionset(
int a,
int b){
return fa[findset(a)]=
findset(b);
}
ll d[maxn],f[maxn][30],dp[maxn][
30][
2];
//dp[i][j][0|1]用来表示向上倍增的最大边，严格次大边
void bfs(){
queue<
int>
q;
q.push(1);
d[1]=
1;
while(!
q.empty()){
int x=
q.front();q.pop();
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(d[y])
continue;
d[y]=d[x]+
1;
f[y][0]=
x;
dp[y][0][
0]=
edge[i].w;
dp[y][0][
1]=-
0x3f3f3f3f;
for(
int k=
1;k<=
29;k++
){
f[y][k]=f[f[y][k-
1]][k-
1];
int a=dp[y][k-
1][
0];
//y向上下一半的最大值
int b=dp[y][k-
1][
1];
//y向上下一半的严格次大值
int c=dp[f[y][k-
1]][k-
1][
0];
//y向上上一半的最大值
int d=dp[f[y][k-
1]][k-
1][
1];
//y向上上一半的严格次大值
dp[y][k][
0]=
max(a,c);
if(a==c)dp[x][k][
1]=
max(b,d);
else if(a>c)dp[x][k][
1]=
max(c,b);
else if(a<c)dp[x][k][
1]=
max(a,d);
}
q.push(y);
}
}
}
inline void calc(ll &val1,ll &val2,ll a,ll b){
//更新最大和次大
if(a<=val1)val2=
max(a,val2);
else val2=val1,val1=
a;
}
int lca(
int x,
int y,
int z){
//处理加入(x,y,z)后的次小生成树
ll val1=-
1,val2=-
1;
if(d[x]<
d[y])swap(x,y);
for(
int i=
29;i>=
0;i--
)
if(d[f[x][i]]>=
d[y]){
calc(val1,val2,dp[x][i][0],dp[x][i][
1]);
x=
f[x][i];
}
if(x==
y){
if(val1!=z)
return val1;
return val2;
}
for(
int i=
29;i>=
0;i--
)
if(f[x][i]!=
f[y][i]){
calc(val1,val2,dp[x][i][0],dp[x][i][
1]);
calc(val1,val2,dp[y][i][0],dp[y][i][
1]);
x=f[x][i],y=
f[y][i];
}
calc(val1,val2,dp[x][0][
0],dp[x][
0][
1]);
calc(val1,val2,dp[y][0][
0],dp[y][
0][
1]);
x=f[x][
0];
if(val1!=z)
return val1;
else return val2;
}
int main(){
int n,m;
scanf("%d%d",&n,&
m);
for(
int i=
0;i<m;i++
)
scanf("%d%d%d",&q[i].u,&q[i].v,&
q[i].w);
sort(q,q+
m);
for(
int i=
1;i<=n;i++) fa[i]=
i;
memset(head,-
1,
sizeof head);
memset(vis,0,
sizeof vis);
tot=
0;
int cnt=
0;
long long ans=
0;
for(
int i=
0;i<m;i++
){
int u=q[i].u,v=
q[i].v;
if(findset(u)==findset(v))
continue;
unionset(u,v);
vis[i]=
1;
addedge(u,v,q[i].w);
addedge(v,u,q[i].w);
ans+=
q[i].w;
if(++cnt==n-
1)
break;
}
bfs();
int z=
0x3f3f3f3f;
for(
int i=
0;i<m;i++
)
if(!
vis[i]) {
int t=
lca(q[i].u,q[i].v,q[i].w);
if(t>
0)z=min(z,-t+
q[i].w);
}
printf("%lld\n",ans+
z);
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10514467.html
