@[5t0_0r2](/user/999274)
```cpp
else if(Max1 < Max[v][i][0]){
Max2 = max(Max1,Max[v][i][1]);//这里要改
Max1 = Max[v][i][0];
}
```
不过还是过不了
by diqiuyi @ 2023-12-14 13:56:03
@[5t0_0r2](/user/999274)
改成这样就过了。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,M = 3e5 + 9,LOGN = 20,INF = LLONG_MAX;
int n,m,sum,ans,k;
struct Edge{
int to,cost,nex;
} e[N << 1];
int top;
int ecnt,head[N];
void addedge(int u,int v,int w){
ecnt++;
e[ecnt] = (Edge){v,w,head[u]};
head[u] = ecnt;
}
struct edge{
int u,v,w;
bool use;
} to_a[M];
int fa[N];
int dep[N];
int anc[N][LOGN + 9];
int Max[N][LOGN + 9][2];
bool cmp(edge x,edge y){
return x.w < y.w;
}
int father(int x){
if(fa[x] == x)
return x;
fa[x] = father(fa[x]);
return fa[x];
}
void join(int x,int y){
int fa_x = father(x),fa_y = father(y);
fa[fa_y] = fa_x;
}
void kruscal(){//kruscal
for(int i = 1;i <= top;i++){
if(father(to_a[i].u) != father(to_a[i].v)){
sum += to_a[i].w;
addedge(to_a[i].u,to_a[i].v,to_a[i].w);
addedge(to_a[i].v,to_a[i].u,to_a[i].w);
join(to_a[i].u,to_a[i].v);
to_a[i].use = true;
}
}
}
void dfs(int u){
dep[u] = dep[anc[u][0]] + 1;//u的深度为父节点的深度+1
for(int i = 1;i <= LOGN;i++){
anc[u][i] = anc[anc[u][i - 1]][i - 1];//这点跟LCA中的一样
if(Max[u][i - 1][0] == Max[anc[u][i - 1]][i - 1][0]){
Max[u][i][0] = Max[u][i - 1][0];
Max[u][i][1] = max(Max[anc[u][i - 1]][i - 1][1],Max[u][i - 1][1]);
}
else if(Max[u][i - 1][0] > Max[anc[u][i - 1]][i - 1][0]){
Max[u][i][0] = Max[u][i - 1][0];
Max[u][i][1] = max(Max[anc[u][i - 1]][i - 1][0],Max[u][i - 1][1]);
}
else if(Max[u][i - 1][0] < Max[anc[u][i - 1]][i - 1][0]){
Max[u][i][0] = Max[anc[u][i - 1]][i - 1][0];
Max[u][i][1] = max(Max[anc[u][i - 1]][i - 1][1],Max[u][i - 1][0]);//改动了
}
}
for(int i = head[u];i;i = e[i].nex){
int v = e[i].to,w = e[i].cost;
if(v == anc[u][0])
continue;
anc[v][0] = u;
Max[v][0][0] = w;
dfs(v);
}
}
int LCA(int u,int v){
if(dep[u] < dep[v])
swap(u,v);
for(int i = LOGN;i >= 0;i--)
if(dep[anc[u][i]] >= dep[v])
u = anc[u][i];
if(u == v)
return u;
for(int i = LOGN;i >= 0;i--){
if(anc[u][i] != anc[v][i]){
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
int cal(int u,int v,int w){
int lca = LCA(u,v);
int Max1 = 0,Max2 = 0;
for(int i = LOGN;i >= 0;i--){
if(dep[anc[u][i]] >= dep[lca]){
if(Max1 == Max[u][i][0])
Max2 = max(Max2,Max[u][i][1]);
else if(Max1 > Max[u][i][0])
Max2 = max(Max2,Max[u][i][0]);
else if(Max1 < Max[u][i][0]){
Max2 = max(Max1,Max[u][i][1]);//改动了
Max1 = Max[u][i][0];
}
u = anc[u][i];
}
if(dep[anc[v][i]] >= dep[lca]){
if(Max1 == Max[v][i][0])
Max2 = max(Max2,Max[v][i][1]);
else if(Max1 > Max[v][i][0])
Max2 = max(Max2,Max[v][i][0]);
else if(Max1 < Max[v][i][0]){
Max2 = max(Max1,Max[v][i][1]);//改动了
Max1 = Max[v][i][0];
}
v = anc[v][i];
}
}
if(w != Max1)
return sum - Max1 + w;
if(Max2)
return sum - Max2 + w;
return INF;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
fa[i] = i;
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
if(u == v)
continue;
to_a[++top] = (edge){u,v,w};
}
sort(to_a + 1,to_a + top + 1,cmp);
kruscal();
dfs(1);
ans = INF;
for(int i = 1;i <= top;i++)
if(!to_a[i].use)
ans = min(ans,cal(to_a[i].u,to_a[i].v,to_a[i].w));
cout << ans;
return 0;
}
```
by diqiuyi @ 2023-12-14 14:01:16