首页 > 代码库 > 次小生成树的模版
次小生成树的模版
求次小生成树的步骤是：
1、求出最小生成树MST,用一个矩阵maxe[u][v]记录在MST中连接u-v的路径中权值最大的边.
2、枚举所有不在T中的边u-v,加入边u-v,删除权值为max[u][v]的边,不断枚举找到次小生成树.
由于邻接矩阵建图无法储存平行边（重边），我们在建图的时候都是取当前最小值。所以用prim做的话，很可能出错。但是prim也是有市场的，当没有平行边，并且定点数比较少的时候，用prim就有优势。如果有平行边，就必须用kruskal。用链式前向星建图。
下面是两个模版，时间复杂度是不同的。不过，貌似时间复杂度相差不大。最大的区别还是平行边。
可以用该模版试试poj1679
//Kruskal
//时间复杂度 O(mlogm + n^2)const int N=1010,M=100010,INF=0x3f3f3f3f;int f[N],r[N];int Find(int x){ if(x==f[x]) return x; return f[x]=Find(f[x]);}void Link(int x,int y){ int a=Find(x), b=Find(y); if(a!=b) { f[b]=a; r[a]+=r[b]; }}struct node{ int u,v,w; bool select;}edge[M];bool cmp(const node &a, const node &b){ if(a.w!=b.w) return a.w<b.w; if(a.u!=b.u) return a.u<b.u; return a.v<b.v;}struct node1{ int to,next;}e[N];int cnt,tot,head[N],en[N],maxe[N][N];//e的边数、头结点、尾结点、两点在mst中的最大边void Kruskal(int n,int m){ int k=0, i,j,t; for(cnt=0;cnt<n;cnt++) { e[cnt].to=cnt+1; e[cnt].next=head[cnt+1]; en[cnt+1]=cnt; head[cnt+1]=cnt; } sort(edge,edge+m,cmp); for(i=0;i<m;i++) { if(k==n-1) break; if(edge[i].w<0) continue; int a=Find(edge[i].u), b=Find(edge[i].v); if(a!=b) { for(j=head[a];j!=-1;j=e[j].next){ for(t=head[b];t!=-1;t=e[t].next){ int u=e[j].to, v=e[t].to; maxe[u][v]=maxe[v][u]=edge[i].w; } } e[en[b]].next=head[a]; en[b]=en[a]; Link(a,b); k++; edge[i].select=1; } }}void addedge(int u,int v,int w){ edge[tot].u=u;edge[tot].v=v;edge[tot].w=w;tot++;}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(en,-1,sizeof(en)); for(int i=0;i<N;i++){ edge[i].select=0; f[i]=i; r[i]=1; }}int main(){ //freopen("test.txt","r",stdin); int mst,secmst; Kruskal(n,m); mst=0; for(i=0;i<m;i++){ if(edge[i].select) mst+=edge[i].w; } secmst=INF; for(i=0;i<m;i++){ if(!edge[i].select) secmst=min(secmst,mst+edge[i].w-maxe[edge[i].u][edge[i].u]]); } return 0;}
prim，时间复杂度是O (2 n^2)
const int maxn=1100,INF=0x3f3f3f3f;int dist[maxn],Map[maxn][maxn],pre[maxn],maxe[maxn][maxn];//向外延伸的最短边长，记录图信息，记录连接信息,最长边bool vis[maxn];//1表示点已经在树的，0表示点在树外bool f[maxn][maxn];//存在边为1，用过为0int n,m;//顶点数目int Prim(){ int i,j,k,Min,ans=0; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); memset(maxe,0,sizeof(maxe)); for(i=2;i<=n;i++) { dist[i]=Map[1][i]; pre[i]=1; } dist[1]=0; vis[1]=1; pre[1]=0; for(i=1;i<n;i++) { Min=INF; k=0; for(j=1;j<=n;j++) { if(!vis[j]&&dist[j]<Min) { Min=dist[j]; k=j; } } if(Min==INF) return -1;//G不连通 vis[k]=1; ans+=Min; f[pre[k]][k] = f[k][pre[k]]=1; for(j=1;j<=n;j++) { if(vis[j]) maxe[k][j]=maxe[j][k]=max(maxe[j][pre[k]],dist[k]); if(!vis[j]&&dist[j]>Map[k][j]) { dist[j]=Map[k][j]; pre[j]=k; } } } return ans;}void init(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { if(i==j)Map[i][j]=0; else Map[i][j]=INF; }}
次小生成树的模版
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。