原博客出处：https://blog.csdn.net/yasola/article/details/74276255
通常次小生成树是使用Prim算法进行实现的，因为可以在Prim算法松弛的同时求得最小生成树上任意两点之间的最长边。但是利用Kruskal算法却没办法在松弛的同时求得。
所以我们就要在Kruskal求完最短路后，对于每个顶点bfs一次，得到树上任意两点的最长边。之后求可以像之前一样枚举不在树上的边，代替找最小值了。
两种方法的时间杂度是一样的，但Kruskal的实现代码回长非常多，不过Kruskal的实现可以处理Prim难以处理的重边。
一、Kruskal模板
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define mem(a,b) memset((a),(b),sizeof(a)) const int MAXV=+;
const int MAXE=+; struct Edge
{
int from,to,cost;
Edge(int f=,int t=,int c=):from(f),to(t),cost(c){}
bool operator<(const Edge &other)const
{
return cost<other.cost;
}
}edge[MAXE]; int V,E,par[MAXV],high[MAXV],the_max[MAXV][MAXV];
bool used[MAXE];//边是否使用的标记
bool vis[MAXV];
vector<pair<int,int> > G[MAXV];//最小生成树 void init()//初始化
{
for(int i=;i<=E;++i)
used[i]=false;
for(int i=;i<=V;++i)
{
par[i]=i;
high[i]=;
G[i].clear();
}
} int findfather(int x)
{
return par[x]=par[x]==x?x:findfather(par[x]);
} bool unite(int a,int b)
{
int fa=findfather(a),fb=findfather(b);
if(fa==fb)
return false;
if(high[fa]>high[fb])
par[fb]=fa;
else
{
par[fa]=fb;
if(high[fa]==high[fb])
++high[fb];
}
return true;
} void bfs(int s)
{
mem(vis,);
vis[s]=true;
the_max[s][s]=;
queue<int> que;
que.push(s);
while(!que.empty())
{
int u=que.front(); que.pop();
for(int i=;i<G[u].size();++i)
{
int v=G[u][i].fi;
if(!vis[v])
{
vis[v]=true;
the_max[s][v]=max(the_max[s][u],G[u][i].se);
the_max[v][s]=the_max[s][v];
que.push(v);
}
}
}
} int main()
{
int T_T;
scanf("%d",&T_T);
for(int cas=;cas<=T_T;++cas)
{
printf("Case #%d : ",cas);
scanf("%d%d",&V,&E);
init();
for(int i=;i<E;++i)
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].cost);
sort(edge,edge+E);
int res=;
for(int i=;i<E;++i)
if(unite(edge[i].from,edge[i].to))
{
res+=edge[i].cost;
used[i]=true;
G[edge[i].from].push_back(make_pair(edge[i].to,edge[i].cost));
G[edge[i].to].push_back(make_pair(edge[i].from,edge[i].cost));
}
bool ok=true;
for(int i=;i<=V;++i)
if(findfather(i)!=findfather())
{
ok=false;
break;
}
if(!ok)//不联通
{
puts("No way");
continue;
}
if(E==V-)//生成树唯一
{
puts("No second way");
continue;
}
for(int i=;i<=V;++i)
bfs(i);
int ans=INF;
for(int i=;i<E;++i)
if(!used[i])
ans=min(ans,res-the_max[edge[i].from][edge[i].to]+edge[i].cost);
printf("%d\n",ans);
} return ;
}
二、prim模板
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=+;
bool link[maxn][maxn],vis[maxn];
int w[maxn][maxn],lowc[maxn],pre[maxn],Max[maxn][maxn];
int n,m;
int prim()
{
int i,j,p,k;
int minc,res=;
memset(vis,false,sizeof(vis));
memset(pre,,sizeof(pre));
memset(Max,,sizeof(Max));
vis[]=true,pre[]=;
for(i=; i<=n; i++) //初始化
{
lowc[i]=w[][i];
pre[i]=;
}
for(i=; i<=n; i++) //prim
{
minc=inf,p=-;
for(j=; j<=n; j++)
{
if(!vis[j]&&lowc[j]<minc)
{
minc=lowc[j];
p=j;
}
}
vis[p]=true;
res+=minc;//最小生成树加权值
Max[pre[p]][p]=minc;//直接相连的两点最大权值就是边权值本身
link[pre[p]][p]=true;//将这两条边标记为最小生成树的边
link[p][pre[p]]=true;
for(k=; k<=n; k++)
Max[k][p]=max(Max[pre[p]][p],Max[k][p]);//非直接相连的最大权值需要不断更新
for(j=; j<=n; j++)
if(!vis[j]&&lowc[j]>w[p][j])
{
lowc[j]=w[p][j];
pre[j]=p;
} }
return res;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int s,e,t,ans,ans1; while(~scanf("%d%d",&n,&m))
{
int i,j;
bool ok=true;//是否唯一最小生成树的标志
for(i=; i<=n; i++)
for(j=; j<=n; j++)
w[i][j]=inf;
memset(link,false,sizeof(link));
for(i=; i<=m; i++)
{
scanf("%d%d%d",&s,&e,&t);
w[s][e]=t;
w[e][s]=t;
}
ans=prim();//最小生成树的权值
for(i=; i<=n; i++)
{
for(j=i+; j<=n; j++)
{
if(w[i][j]!=inf&&!link[i][j])
{
ans1=ans+w[i][j]-Max[i][j];//ans1次小生成树的权值
}
if(ans1==ans)
{
ok=;
break;
}
}
if(!ok)
break;
}
printf("ans=%d ans1=%d\n",ans,ans1);
}
return ;
}