首页 > 代码库 > 次小生成树
次小生成树
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1416
求最小生成树和次小生成树，有则输出权值，没有则输出-1
题目保证没有重边
次小生成树prim求法：
次小生成树可由最小生成树换掉一条边求得
先用prim算出最小生成树
prime过程中，
1、因为求次小生成树时，新的边不能是最小生成树中的，所以用一bool数组con记录，
一开始若i，j之间有边 con[i][j]=true，prim过程中，用了边i，j con[i][j]=false
2、因为要换掉最小生成树中的一条边，
prim过程中，用数组maxn[i][j]记录最小生成树中，i到j之间单条边的最大权值
求完最小生成树后，枚举每一条con=true的边，假设他连接i，j
新的生成树的权值和=最小生成树的权值和-maxn[i][j]+这条边的权值
所有新的生成树取最小值，就是次小生成树
在注意一点，边是双向边，所以修改数组的时候改2个
如何在prim过程中，维护con和maxn数组？
用一数组pre[i]=j， 表示最小生成树中点i的前驱是j
最次找到minn最小的一个点k后，
con[pre[k]][k]=con[k][pre[k]]=false;
maxn[pre[k]][k]=maxn[k][pre[k]]=minn[k];
用点k去更新其他点j的minn时，
若j在最小生成树中，maxn[k][j]=maxn[j][k]=max(maxn[j][pre[k]],maxn[pre[k]][k]);
当j不在最小生成树中，且j能被k更新时，pre[j]=k
三种特殊情况：
1、原图不连通，prim找不到n-1条边，即代码中的nott
2、图本身就是一棵树，那么做完最小生成树后，所有的con[][]=false
3、图有重边（平行边），
那就要更改con数组，设int con[i][j]，表示链接i，j 且 不在最小生成树中的最大权值
建立2个二维数组，一个存储原图中两点之间的最小权值，另一个存储次小权值
当prim里选定一条边后，不是将con[i][j]改为false，而是改为次小权值
kruscal算法求法：
http://www.cppblog.com/MatoNo1/archive/2011/05/29/147627.aspx
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,a[501][501],minn[501],maxn[501][501],pre[501],mst,ans=1e7;bool v[501],con[501][501];int main(){ scanf("%d%d",&n,&m); memset(a,127,sizeof(a)); int u,r,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&r,&w); a[u][r]=a[r][u]=w; con[u][r]=con[r][u]=true; } bool nott=false; memset(minn,127,sizeof(minn)); for(int i=1;i<=n;i++) { pre[i]=1; minn[i]=a[1][i]; } minn[1]=0; v[1]=true; for(int i=1;i<n;i++) { int k=0; for(int j=1;j<=n;j++) if(minn[j]<minn[k]&&!v[j]) k=j; if(!k) { nott=true; break; } v[k]=true; mst+=minn[k]; con[pre[k]][k]=con[k][pre[k]]=false; maxn[pre[k]][k]=maxn[k][pre[k]]=minn[k]; for(int j=1;j<=n;j++) if(v[j]&&j!=k) maxn[k][j]=maxn[j][k]=max(maxn[j][pre[k]],maxn[pre[k]][k]); else if(!v[j]&&minn[j]>a[k][j]) {minn[j]=a[k][j]; pre[j]=k;} } if(nott) { printf("Cost: -1\nCost: -1"); return 0; } printf("Cost: %d\n",mst); for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(con[i][j]) ans=min(ans,a[i][j]-maxn[i][j]); if(ans==1e7) printf("Cost: -1"); else printf("Cost: %d\n",ans+mst); }
次小生成树