poj 1679 次小生成树

次小生成树的求法:

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=0;memset(vi,0,sizeof(vi));memset(pre,-1,sizeof(pre));for(i=1;i<=n;i++)dist[i]=inf;//一定要初始化为inf，这样以第一个点开始，使与第一个相连的节点的前节点为第一个节点。dist[1]=0;//以第一个节点开始for(i=1;i<=n;i++){Min=inf;for(j=1;j<=n;j++){if(!vi[j]&&dist[j]<Min){Min=dist[j];index=j;}}if(pre[index]!=-1)//如果存在前节点
        {use[index][pre[index]]=use[pre[index]][index]=USE;//标记为使用过for(j=1;j<=n;j++)if(vi[j])//对树种已存在的点进行更新f[j][index]=max(f[j][pre[index]],map[index][pre[index]]);}ans+=Min;vi[index]=1;//cout<<Min<<"*"<<endl;for(j=1;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=1;i<=n;i++)for(j=1;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,0,sizeof(f));for(i=1;i<=Maxn-1;i++)for(j=1;j<=Maxn-1;j++)map[i][j]=map[j][i]=inf;memset(use,0,sizeof(use));
}
int main()
{int i,j,a,b,c,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);map[a][b]=map[b][a]=c;use[a][b]=use[b][a]=1;}int ans1=prime(1);int ans2=secondmst(ans1);if(ans1==ans2)printf("Not Unique!\n");elseprintf("%d\n",ans1);}return 0;
}

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[10010];
int set[102],e,vi[10010],p[110],index;
int find(int x)
{if(x!=set[x])set[x]=find(set[x]);return set[x];
}
void init()
{e=0;index=0;for(int i=0;i<=101;i++)set[i]=i;memset(vi,0,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=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);edge[i].x=x,edge[i].y=y,edge[i].c=c;}sort(edge+1,edge+m+1);int num=0;int ans=0;for(i=1;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-1)break;}int ans2=0,num2=0;int f=0;for(i=0;i<index;i++)//在枚举每次删除一条边后，求最小生成树
        {for(j=0;j<=101;j++)set[j]=j;ans2=0,num2=0;for(j=1;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-1)break;}if(num2!=n-1)continue;if(ans==ans2)//若删除某条边后的最小权值与原来相同，那么最小生成树不唯一
            {f=1;break;}}if(!f)printf("%d\n",ans);elseprintf("Not Unique!\n");}return 0;
}