C++ 代码
/*
步骤:
1.求最小生成树,将树边连接起来,标记非树边
2.预处理出dist1[a][b],dist2[a][b]
dist1[a][b]-->代表的是a->b路径上经过的边权最大的那个边的边权
dist2[a][b]-->代表的是a->b路径上经过的边权次大的那个边的边权
预处理的方法是以1-n每个节点依次作为根,进行dfs,maxd1,maxd2代表还没有枚举i节点的
子节点时候,根节点i到上一层u路径上的最大边权,到了这一层,就要看每个u->son的w看看
能不能更新maxd1,maxd2
Notes:
由于同一层的所有子节点都要用到上一层到u节点的maxd1,maxd2,所以应该用t1,t2将maxd1,maxd2
保存,修改t1,t2,而不是直接修改maxd1,maxd2,因为直接修改的话,后面的子节点用的就不是到
父节点u的maxd1,maxd2了
for(int i=1;i<=n;i++)
dfs(i,u,fa,maxd1,maxd2,d1[i],d2[i])
3.依次枚举每个非树边,a->b(边权w)
因为就缺这条边,a->b就形成环了,所以a->b路径上的其他边都在树上
(1)如果w>dist1[a][b],说明w是a->b之间最大的边,用它替换树上a->b最大的边,t=sum+w-dist1[a][b]
(2)如果w>dist2[a][b],此时一定说明了w==dist1[a][b]
因为如果w<dist1[a][b]的话,就轮不到dist1[a][b]来当最小生成树上的那个边了
所以此时用w替换次大边就行了 t=sum+w-dist2[a][b]
结果:res=min(res,t)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510,M = 10010;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int dist1[N][N],dist2[N][N];
int p[N];
int n,m;
struct Edge{
int a,b,w;
bool flag;
bool operator<(const Edge& e)const
{
return w<e.w;
}
}edge[M];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
//s是根节点,s->u上的路径上出现过的最大边权就是dist1[s][u],出现过的次大边权就是dist2[s][u]
void dfs(int s,int u,int fa,int maxd1,int maxd2,int d1[][N],int d2[][N])
{
d1[s][u]=maxd1,d2[s][u]=maxd2;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
int t1=maxd1,t2=maxd2;
if(w[i]>t1) {t2=t1;t1=w[i];}
else if(w[i]<t1 && w[i]>t2) {t2=w[i];}//严格次大
dfs(s,j,u,t1,t2,d1,d2);
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
sort(edge,edge+m);
//1.kruskal算法建树
for(int i=1;i<=n;i++) p[i]=i;
LL sum=0;//最小生成树权值
for(int i=0;i<m;i++)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
add(a,b,w);
add(b,a,w);
edge[i].flag=true;
sum+=w;
}
}
//2.dfs预处理a->b路径上的经过的最大边权和次大边权dist1[a][b],dist2[a][b]
//初始dist1[i][i]=0,dist2[i][i]不存在
for(int i=1;i<=n;i++) dfs(i,i,-1,0,-1e9,dist1,dist2);
//3.依次枚举每个非树边,看看能不能替换原来最小生成树中的某个边
//将所有能替换的情况取一个最小值,就是次小生成树
LL res=1e18;
for(int i=0;i<m;i++)
{
if(!edge[i].flag)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
LL t=0;
if(w>dist1[a][b]) t=sum+w-dist1[a][b];
else if(w>dist2[a][b]) t=sum+w-dist2[a][b];
if(t) res=min(res,t);
}
}
cout<<res<<endl;
return 0;
}