首页 > 代码库 > UVA 10600 & 次小生成树

UVA 10600 & 次小生成树

2024-07-12 16:05:21   215人阅读

这道题涉及次小生成树，有必要先弄明白次小生成树是怎么一回事。

次小生成树，顾名知义。一个定理是，次小生成树可以由最小生成树交换一条边得到。这怎么证明，可以上网搜一下。但有必要提醒的是，交换过来的这样一条边，必须是未成使用过的（即不是最小生成树的边）。而且，交换走的边，必须是已存在的，而且是两点间最短路径的最大边权的边。

所以，可以在求最小生成树时求这最大边权的边。

 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 }
View Code

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 }
View Code


联系
我们