算法1
/
* 使用克鲁斯卡尔算法先生成最小生成树
* 由定理证明可知 次小生成树最多只用换掉最小生成树中的一条边(本题要求绝对次小生成树 我们选出的非树边要比换掉的树边至少大1)
* 在任意添加一条边之后 如A-B 那么A-B会形成一个环路 那么由于生成次小生成树 则需要换掉环路中值最大的边
* 对于重边的情况使用上条策略仍然成立
* 由于需要生成绝对次小生成树 那么当最大值与我们挑出的非树边相等时那么 我们需要换掉树中的次小边才能保证此次换边生成的是次小生成树
* 深度优先搜索找出树中A 到 B 的最大边与最小边即可
* /
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=510,M=1e4+10,E=M*2;
int n,m;
int h[N],e[E],ne[E],w[E],idx=0;
int p[N];
struct link{
int a,b,c;
bool operator< (const link &w) const{
return c<w.c;
}
}edge[M];
queue<link> q;
int dist[N][N][2];
bool st[N];
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(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void dfs(int x,int u,int val){
st[u]=true;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(st[j]==true) continue;
if(w[i]>val){
dist[x][j][0]=w[i];//更新最大值
dist[x][j][1]=val;//更新次大值
}else if(w[i]==val){
dist[x][j][0]=val;
dist[x][j][1]=dist[x][u][1];//此时次大值则为父节点的次大值
}else if(w[i]<val){
dist[x][j][0]=val;
dist[x][j][1]=max(dist[x][u][1],w[i]);//此时次大值为父节点的次大值与当前加入边的次大值的最大值
}
dfs(x,j,dist[x][j][0]);
}
}
int main(){
long long val=0;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge[i]={a,b,c};
}
sort(edge,edge+m);
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++){
int a=edge[i].a,b=edge[i].b,c=edge[i].c;
int a1=find(a),b1=find(b);
if(a1==b1) {
q.push({a,b,c});
continue;
}
p[a1]=b1;
val+=c;
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=n;i++)
{
memset(st,0,sizeof st);
dfs(i,i,0);
}
int res=0x3f3f3f3f;
while(q.size()){
auto t=q.front();
q.pop();
int a=t.a,b=t.b,c=t.c;
if(c>dist[a][b][0]){
res=min(res,c-dist[a][b][0]);
}else if(c==dist[a][b][0]){
res=min(res,c-dist[a][b][1]);
}
}
cout<<val+res;
}