求次小生成树思路： 先把最小生成树求出来 用一个Max[i][j] 数组把 i点到j 点的道路中 权值最大的那个记录下来 used数组记录该条边有没有被最小生成树使用过 把没有使用过的一条边加入最小生成树必然回形成一条回路 在这条回路中减去 除加入的边的权值最大的一条边 原图必然保持连通 （如果此时 权值最大的边和新加入的边权值相同 则存在 不同的最小生成树） 把每一条边加入再删除后 即可得出次小生成树
参考了： https://blog.csdn.net/qq_33951440/article/details/53084248
https://blog.csdn.net/li1615882553/article/details/80011884
https://www.cnblogs.com/kuangbin/p/3147329.html
#include <cstdio> #include <cmath> #include <algorithm> #include<vector> #include<iostream> #include<cstring> int ans; const int maxn=1000+10; const int INF=100000000; int x[maxn],y[maxn]; int cost[maxn][maxn]; int pre[maxn]; int lowc[maxn]; int Max[maxn][maxn]; int vis[maxn]; int parent[maxn]; int used[maxn][maxn]; using namespace std; int prim(int cost[][maxn],int n){ int ans=0; memset(vis,false,sizeof(vis)); memset(Max,0,sizeof(Max)); memset(used,false,sizeof(used)); vis[0]=1; pre[0]=-1; for(int i=1;i<n;i++){ lowc[i]=cost[0][i];//刚开始只有v0在生成树中 生成树和不在生成树的距离 就是v0和 其他点的距离 pre[i]=0; } for(int i=1;i<n;i++){ int minc=INF; int p=-1; for(int j=0;j<n;j++){ if(!vis[j]&&minc>lowc[j]){//找出到树最短的变 minc=lowc[j]; p=j; } } if(p==-1)return -1; //不连通 ans+=minc; vis[p]=1; used[p][pre[p]]=used[pre[p]][p]=1; //该边设置为已使用 for(int j=0;j<n;j++){ if(vis[j])Max[j][p]=Max[p][j]=max(Max[j][pre[p]],minc);//更新 j到p 的最大权值的边 if(!vis[j]&&lowc[j]>cost[p][j]){ lowc[j]=cost[p][j]; //更新树到点的最短距离 pre[j]=p;//j点如果要进树 连p点 所以p就是j的父结点 } } } return ans; } int smst(int cost[][maxn],int n){ //计算是否可以删除一条边 仍得到所有边权值不变 int minnum=INF; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(cost[i][j]!=INF&&!used[i][j]){ minnum=min(minnum,ans+cost[i][j]-Max[i][j]); } } } return minnum; } int main() { int t; cin>>t; while(t--){ int n,m; scanf("%d%d",&n,&m); int u,v,w; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j)cost[i][j]=0; else cost[i][j]=INF; } } while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--,v--; cost[u][v]=cost[v][u]=w; } ans=prim(cost,n); if(ans==smst(cost,n)){ printf("Not Unique! "); } else printf("%d ",ans); } return 0; }