首先要知道怎么求非严格次小生成树
记为u，v 路径上的最大边权
先求一遍最小生成树，记权值为mins
然后枚举所有不在树中的边
非严格次小生成树的权值为
用倍增或树剖都可以求
现在要求严格次小的
于是记录的次大边权，保证其严格小于最大值，记为
然后依旧是枚举所有不在树中的边
若，则为，否则为1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int N=100050,rt=1;
const LL INF=1LL<<60;
LL mins=0,ans=INF;
int fa[N][25],w[N][25],c[N][25],log[N];
int dep[N],n,m,f[N],used[N<<2];
struct edge{int u,v,val;}t[N<<2];
vector<int> e[N],g[N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
bool cmp(edge a,edge b){return a.val<b.val;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void unite(int u,int v){f[find(u)]=find(v);}
void add(int u,int v,int val)
{
e[u].push_back(v);
g[u].push_back(val);
}
void dfs(int o)
{
for(int i=1;i<=log[dep[o]];i++)
{
fa[o][i]=fa[fa[o][i-1]][i-1];
w[o][i]=max(w[o][i-1],w[fa[o][i-1]][i-1]);
c[o][i]=max(c[o][i-1],c[fa[o][i-1]][i-1]);
if (w[o][i-1]<w[fa[o][i-1]][i-1])
c[o][i]=max(c[o][i],w[o][i-1]);
if (w[o][i-1]>w[fa[o][i-1]][i-1])
c[o][i]=max(c[o][i],w[fa[o][i-1]][i-1]);
}
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (!dep[to])
{
dep[to]=dep[o]+1;
fa[to][0]=o;
w[to][0]=g[o][i];
dfs(to);
}
}
}
int calc(int u,int v,int val)
{
int ret=0;
if (dep[u]<dep[v]) swap(u,v);
for(int i=0;i<=log[dep[u]];i++)
if (((dep[u]-dep[v])>>i)&1)
{
ret=max(ret,val!=w[u][i]?w[u][i]:c[u][i]);
u=fa[u][i];
}
if (u==v) return ret;
for(int i=log[dep[u]];i>=0;i--)
if (fa[u][i]!=fa[v][i])
{
ret=max(ret,val!=w[u][i]?w[u][i]:c[u][i]);
ret=max(ret,val!=w[v][i]?w[v][i]:c[v][i]);
u=fa[u][i],v=fa[v][i];
}
ret=max(ret,val!=w[u][0]?w[u][0]:c[u][0]);
ret=max(ret,val!=w[v][0]?w[v][0]:c[v][0]);
return ret;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
log[i]=log[i-1]+(1<<log[i-1]==i);
for(int i=1;i<=m;i++)
{
t[i].u=read();
t[i].v=read();
t[i].val=read();
}
sort(t+1,t+m+1,cmp);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int u=t[i].u,v=t[i].v;
if (find(u)!=find(v))
{
used[i]=1;
add(u,v,t[i].val);
add(v,u,t[i].val);
unite(u,v);
mins+=t[i].val;
}
}
dep[rt]=1,dfs(rt);
for(int i=1;i<=m;i++)
if (!used[i])
{
int u=t[i].u,v=t[i].v;
int val=calc(u,v,t[i].val);
ans=min(ans,mins-val+t[i].val);
}
printf("%lld",ans);
return 0;
}