次小生成树的求法:
1.Prime法
定义一个二维数组F[i][j]表示点i到点j在最小生成树中的路径上的最大权值。有个知识就是将一条不在最小生成树中的边Edge加入最小生成树时，树中要去掉的边就是Edge连接的两个端点i,j的F[i][j]。这样就能保存找到的生成树时次小生成树。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 1<<30
#define Maxn 102
#define Maxm 10010
#define USE 2
#define EXIST 1
#define NOTEXIST 0
using namespace std;
int map[Maxn][Maxn],dist[Maxn],vi[Maxn],f[Maxn][Maxn],use[Maxn][Maxn],pre[Maxn];
int n,m;
int prime(int src)
{
int i,j,Min,index;
int ans=;
memset(vi,,sizeof(vi));
memset(pre,-,sizeof(pre));
for(i=;i<=n;i++)
dist[i]=inf;//一定要初始化为inf，这样以第一个点开始，使与第一个相连的节点的前节点为第一个节点。
dist[]=;//以第一个节点开始
for(i=;i<=n;i++)
{
Min=inf;
for(j=;j<=n;j++)
{
if(!vi[j]&&dist[j]<Min)
{
Min=dist[j];
index=j;
}
}
if(pre[index]!=-)//如果存在前节点
{
use[index][pre[index]]=use[pre[index]][index]=USE;//标记为使用过
for(j=;j<=n;j++)
if(vi[j])//对树种已存在的点进行更新
f[j][index]=max(f[j][pre[index]],map[index][pre[index]]);
}
ans+=Min;
vi[index]=;
//cout<<Min<<"*"<<endl;
for(j=;j<=n;j++)
{
if(!vi[j]&&dist[j]>map[index][j])
{
dist[j]=map[index][j];
pre[j]=index;
}
}
}
//cout<<ans<<"*"<<endl;
return ans;
}
int secondmst(int mst)
{
int i,j,ans;
ans=inf;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(use[i][j]==EXIST)
{
if(mst+map[i][j]-f[i][j]<ans)//求次小生成树
ans=mst+map[i][j]-f[i][j];
}
//cout<<ans<<"*"<<endl;
return ans;
}
void init()//初始化
{
int i,j;
memset(f,,sizeof(f));
for(i=;i<=Maxn-;i++)
for(j=;j<=Maxn-;j++)
map[i][j]=map[j][i]=inf;
memset(use,,sizeof(use));
}
int main()
{
int i,j,a,b,c,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
use[a][b]=use[b][a]=;
}
int ans1=prime();
int ans2=secondmst(ans1);
if(ans1==ans2)
printf("Not Unique!\n");
else
printf("%d\n",ans1);
}
return ;
}
kruskaer的算法就相对简单，就是先求一边最下生成树，将树中的边保存下来。然后每次去掉一个边，重求最小生成树，找出最小的便是次小生成树。
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct Edge{
int x,y,c;
int operator <(const Edge &temp) const
{
return c<temp.c;
}
}edge[];
int set[],e,vi[],p[],index;
int find(int x)
{
if(x!=set[x])
set[x]=find(set[x]);
return set[x];
}
void init()
{
e=;
index=;
for(int i=;i<=;i++)
set[i]=i;
memset(vi,,sizeof(vi));
}
int main()
{
int t,n,m,i,j,x,y,c;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
edge[i].x=x,edge[i].y=y,edge[i].c=c;
}
sort(edge+,edge+m+);
int num=;
int ans=;
for(i=;i<=m;i++)//先求一边最小生成树
{ //cout<<edge[i].c<<"*"<<endl;
x=find(edge[i].x);
y=find(edge[i].y);
if(x==y)
continue;
p[index++]=i;//将树中的每条边保存起来
set[x]=y;
ans+=edge[i].c;
num++;
if(num==n-)
break;
}
int ans2=,num2=;
int f=;
for(i=;i<index;i++)//在枚举每次删除一条边后，求最小生成树
{
for(j=;j<=;j++)
set[j]=j;
ans2=,num2=;
for(j=;j<=m;j++)
{
if(j==p[i])
continue;
x=find(edge[j].x);
y=find(edge[j].y);
if(x==y)
continue;
set[x]=y;
ans2+=edge[j].c;
num2++;
if(num2==n-)
break;
}
if(num2!=n-)
continue;
if(ans==ans2)//若删除某条边后的最小权值与原来相同，那么最小生成树不唯一
{
f=;
break;
}
}
if(!f)
printf("%d\n",ans);
else
printf("Not Unique!\n");
}
return ;
}