- 题目思路：先搞一个最小生成树，把用到的边做一个标记，然后跑一遍LCA预处理，但是要倍增维护一个最大值和一个次大值。弄完后枚举MST没用到的边，求出两个值——一个是一点到这两点LCA的边权最大值，另一个是另一个点到LCA的边权最大值。然后比较一下取min。
- 代码
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
ll sc() {
ll xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
struct EDGE {
ll u,v,dis;
bool operator < (const EDGE &x) const {
return dis<x.dis;
}
}a[Maxm*2];
struct TREE {
ll next,to,dis;
}edge[Maxn*2];
ll n,m,cnt,ans,num;
ll head[Maxn*2],father[Maxn],deep[Maxn];
bool vis[Maxm];
ll f[Maxn][22];
ll ma[Maxn][22][3];
namespace DY {
void ADD(ll from,ll to,ll dis) {
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
ll find(ll x) {
return x==father[x]? x: father[x]=find(father[x]);
}
void D_F(ll son,ll fa) {
deep[son]=deep[fa]+1;
for(int i=head[son]; i; i=edge[i].next) {
ll to=edge[i].to;
if(to==fa) continue;
ma[to][0][0]=edge[i].dis;
ma[to][0][1]=-INF;
f[to][0]=son;
D_F(to,son);
}
}
void d_f() {
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++) {
f[j][i]=f[f[j][i-1]][i-1];
ma[j][i][0]=max(ma[j][i-1][0], ma[f[j][i-1]][i-1][0]);
ma[j][i][1]=max(ma[j][i-1][1], ma[f[j][i-1]][i-1][1]);
if(ma[j][i-1][0]>ma[f[j][i-1]][i-1][0])
ma[j][i][1]=max(ma[j][i][1], ma[f[j][i-1]][i-1][0]);
else if(ma[j][i-1][0]<ma[f[j][i-1]][i-1][0])
ma[j][i][1]=max(ma[j][i][1], ma[j][i-1][0]);
}
}
ll LCA(ll x,ll y) {
if(deep[x]<deep[y]) swap(x,y);
for(int i=18; i>=0; i--)
if(deep[f[x][i]]>=deep[y])
x=f[x][i];
if(x==y) return y;
for(int i=18; i>=0; i--) {
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
ll calc(ll u,ll v,ll maxx) {
ll res=-INF;
for(int i=18; i>=0; i--) {
if(deep[f[u][i]]>=deep[v]) {
if(maxx!=ma[u][i][0])
res=max(res,ma[u][i][0]);
else res=max(res,ma[u][i][1]);
u=f[u][i];
}
}
return res;
}
void AKNOIP() {
n=sc(); m=sc();
for(int i=1; i<=m; i++) {
a[i].u=sc(); a[i].v=sc(); a[i].dis=sc();
}
for(int i=1; i<=n; i++)
father[i]=i;
sort(a+1,a+1+m);
for(int i=1; i<=m; i++) {
ll aa=find(a[i].u);
ll bb=find(a[i].v);
if(aa!=bb) {
num+=a[i].dis;
father[aa]=bb;
ADD(a[i].u,a[i].v,a[i].dis);
ADD(a[i].v,a[i].u,a[i].dis);
vis[i]=1;
}
}
ma[1][0][1]=-INF;
D_F(1,0);
d_f();
ans=INF;
for(int i=1; i<=m; i++) {
if(!vis[i]) {
ll lca=LCA(a[i].u,a[i].v);
ll maxu=calc(a[i].u,lca,a[i].dis);
ll maxv=calc(a[i].v,lca,a[i].dis);
ans=min(ans,num-max(maxu,maxv)+a[i].dis);
}
}
printf("%lld",ans);
}
};
int main() {
DY::AKNOIP();
return 0;
}