首页 > 代码库 > UVA 10600 & 次小生成树
UVA 10600 & 次小生成树
这道题涉及次小生成树,有必要先弄明白次小生成树是怎么一回事。
次小生成树,顾名知义。一个定理是,次小生成树可以由最小生成树交换一条边得到。这怎么证明,可以上网搜一下。但有必要提醒的是,交换过来的这样一条边,必须是未成使用过的(即不是最小生成树的边)。而且,交换走的边,必须是已存在的,而且是两点间最短路径的最大边权的边。
所以,可以在求最小生成树时求这最大边权的边。
1 void prim(){ 2 memset(f,0,sizeof(f)); 3 least[1]=0; 4 for(int i=2;i<=n;i++){ 5 least[i]=map[1][i]; 6 if(least[i]!=inf) 7 pre[i]=1; 8 } 9 vis[1]=true;10 for(int i=1;i<=n;i++){11 int min=inf,p=-1;12 for(int k=1;k<=n;k++){13 if(least[k]<min&&!vis[k]){14 p=k; min=least[k];15 }16 }17 18 if(p==-1) return ;19 ans1+=min;20 used[pre[p]][p]=used[p][pre[p]]=1;21 for(int j=1;j<=n;j++){ //应该是已访问的点,这样边是已使用22 if(vis[j])23 f[j][p]=max(f[j][pre[p]],map[pre[p]][p]);24 f[p][j]=f[j][p];25 }26 vis[p]=true;27 for(int k=1;k<=n;k++){28 if(!vis[k]&&map[p][k]<least[k]){29 least[k]=map[p][k];30 pre[k]=p;31 }32 }33 }34 }
UV10600是裸的次小生成树题。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 const int MAXN=105; 8 const int inf=10000000; 9 int map[MAXN][MAXN]; int f[MAXN][MAXN];10 bool exist[MAXN][MAXN],used[MAXN][MAXN];11 int least[MAXN],pre[MAXN]; bool vis[MAXN]; 12 int n,m,ans1,ans2;13 14 void prim(){15 memset(f,0,sizeof(f));16 least[1]=0;17 for(int i=2;i<=n;i++){18 least[i]=map[1][i];19 if(least[i]!=inf)20 pre[i]=1;21 }22 vis[1]=true;23 for(int i=1;i<=n;i++){24 int min=inf,p=-1;25 for(int k=1;k<=n;k++){26 if(least[k]<min&&!vis[k]){27 p=k; min=least[k];28 }29 }30 31 if(p==-1) return ;32 ans1+=min;33 used[pre[p]][p]=used[p][pre[p]]=1;34 for(int j=1;j<=n;j++){35 if(vis[j])36 f[j][p]=max(f[j][pre[p]],map[pre[p]][p]);37 f[p][j]=f[j][p];38 }39 vis[p]=true;40 for(int k=1;k<=n;k++){41 if(!vis[k]&&map[p][k]<least[k]){42 least[k]=map[p][k];43 pre[k]=p;44 }45 }46 }47 }48 49 void secondT(){50 ans2=inf;51 for(int i=1;i<=n;i++){52 for(int j=1;j<=n;j++){53 if(exist[i][j]&&!used[i][j]&&ans1 + map[i][j] - f[i][j] < ans2)54 ans2=ans1 + map[i][j] - f[i][j];55 }56 }57 }58 59 int main(){60 int T; 61 scanf("%d",&T);62 while(T--){63 scanf("%d%d",&n,&m);64 int u,v,d;65 ans1=ans2=0;66 memset(exist,-1,sizeof(exist));67 for(int i=1;i<=n;i++){68 for(int j=i;j<=n;j++)69 map[i][j]=map[j][i]=inf;70 }71 for(int i=1;i<=m;i++){72 scanf("%d%d%d",&u,&v,&d);73 map[u][v]=map[v][u]=d;74 exist[u][v]=exist[v][u]=1;75 }76 memset(pre,-1,sizeof(pre));77 memset(used,0,sizeof(used));78 memset(vis,false,sizeof(vis));79 prim();80 secondT();81 printf("%d %d\n",ans1,ans2);82 }83 return 0;84 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。