例题:https://vjudge.net/problem/POJ-1679
算法描述:关于次小生成树,首先求出最小生成树,然后枚举每条不在最小生成树上的边(在原本的节点上添加一个vis属性进行判断即可),并把这条边放到最小生成树上面,然后就一定会形成环,那么我们在这条环路中取出一条(除了新加入的那一条边)最长的路。利用二维数组d[][]来维护环路中最长的路径。最后依次遍历每条未加入最小生成树的边,即可求出次小生成树。


关于这个算法有些地方还没想明白,特别是合并路径那一块的代码的具体含义我不太清楚,先放个板子在这吧!
:)
已更新完毕,大致弄明白了,这个p[N]存在的意义主要是实现对d[N][N]的实时更新,第49行的功能也就显而易见了,p[N]要保存所有点和其相关点的关系,说到底,其实就是一个邻接表的实现。

—————————————————————————————————

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=2e2+5,M=1e5+5;
struct rec{
    int x,y,z;
    bool vis;
}edge[M];
int fa[N],d[N][N];
vector<int> p[N];//拓展路径,其实是寻找关联节点
int n,m,t,k;
bool operator<(rec a,rec b){
    return a.z<b.z;
} 
int get(int x){
    if(x==fa[x])    return x;
    return fa[x]=get(fa[x]);
}
int main(){
    scanf("%d",&t);
    while(t--){
        k=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            p[i].clear();
            p[i].push_back(i);
            fa[i]=i;
        }
        for(int i=1;i<=m;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            edge[++k].x=x,edge[k].y=y,edge[k].z=z,edge[k].vis=false;
        }
        sort(edge+1,edge+1+k);
        int ans=0;
        for(int i=1;i<=k;i++){
            int x=get(edge[i].x),y=get(edge[i].y);
            if(x==y)    continue;
            ans+=edge[i].z;
            fa[x]=y;
            edge[i].vis=true;
            int l1=p[x].size(),l2=p[y].size();
            for(int j=0;j<l1;j++)
                for(int k=0;k<l2;k++)    d[p[x][j]][p[y][k]]=d[p[y][k]][p[x][j]]=edge[i].z;
//由kru算法的特性,遍历到的边只会愈来愈大,故能只需等于当前数值即可更新两点间的最大边权
            for(int j=0;j<l1;j++)    p[y].push_back(p[x][j]);
//合并路径,由于fa[x]=y,寻找与x相关的y是可以直接找到的,故只要添加与y关联的x即可
        }
        int ans_2=0x3f3f3f3f;
        for(int i=1;i<=k;i++)
            if(!edge[i].vis)    ans_2=min(ans_2,ans+edge[i].z-d[edge[i].x][edge[i].y]);
        if(ans_2>ans)    printf("%d\n",ans);
        else            printf("Not Unique!\n");    
    }
    return 0;
}