POJ1679

首先求出最小生成樹，記錄權(quán)值之和為MinST。然后枚舉添加邊(u,v)，加上后必形成一個環(huán)，找到環(huán)上非(u,v)邊的權(quán)值最大的邊，把它刪除，計算當(dāng)前生成樹的權(quán)值之和，取所有枚舉加邊后生成樹權(quán)值之和的最小值

?

?

思路：?

最小生成樹唯一性判斷，求次小生成樹的val再與最小生成樹比較。
1.先用prim算法求出最小生成樹。并在其過程中保存加入到MST中的Max[i][j]（ i 到 j 路徑中的最大邊 ）?
2.對未加入MST的邊進行遍歷：從MST中去掉i j路徑中的最大邊，加入未訪問邊G[i][j]，如果得到的生成樹的權(quán)值和MST的相等，則存在次小生成樹的權(quán)值=MST的權(quán)值和

1 #include <algorithm> 2 #include <iostream> 3 #include <cstdio> 4 #include <cmath> 5 #include <cstring> 6 using namespace std; 7 #define INF 0x3f3f3f3f 8 9 const int N = 1e3+6; 10 int G[N][N]; // graph matrix 11 int f[N]; // pre node 12 int vis[N]; // visited node 13 int dis[N]; // main matrix: the edges(set-u) 14 int mark[N][N]; 15 int Max[N][N]; // path from i to j max edge 16 int n,m,best; 17 18 int prim(int v) 19 { 20 int ans=0; 21 vis[v]=1; 22 for(int i=1;i<=n;i++) 23 { 24 dis[i]=G[v][i]; 25 f[i]=v; 26 } 27 dis[v]=0; 28 for(int i=1;i<n;i++) // n-1 29 { 30 int u=-1; 31 for(int j=1;j<=n;j++) 32 if(!vis[j]&&(u==-1||dis[j]<dis[u]))u=j; 33 if(u==-1)break; 34 vis[u]=1; 35 mark[u][f[u]] = mark[f[u]][u] = 1; 36 ans += dis[u]; 37 for(int j=1;j<=n;j++) 38 { 39 // compare with visited node record path max edge 40 if(vis[j])Max[u][j]=Max[j][u]=max(Max[j][f[u]],dis[u]); 41 if(!vis[j]&&dis[j]>G[u][j]) 42 { 43 dis[j]=G[u][j]; 44 f[j]=u; 45 } 46 } 47 } 48 return ans; 49 } 50 51 int SMST() 52 { 53 int mini=INF; 54 for(int i=1;i<=n;i++) 55 for(int j=1;j<=n;j++) //or for(int j=i+1;j<=n;j++) 56 { 57 if(i!=j&&!mark[i][j]) 58 mini = min(mini,best+G[i][j]-Max[i][j]); 59 } 60 return mini; 61 } 62 63 int main() 64 { 65 int x,y,w,T; 66 scanf("%d",&T); 67 while(T--) 68 { 69 memset( vis, 0 ,sizeof(vis) ); 70 memset( Max, 0 ,sizeof(Max) ); 71 memset( f, 0 ,sizeof(f) ); 72 memset( dis, 0 ,sizeof(dis) ); 73 memset( mark, 0 ,sizeof(mark) ); 74 scanf("%d%d",&n,&m); 75 for(int i=1;i<=n;i++) 76 for(int j=1;j<=n;j++) 77 { 78 if(i==j)G[i][j]==0; 79 else G[i][j]=INF; 80 } 81 for(int i=0;i<m;i++) 82 { 83 scanf("%d%d%d",&x,&y,&w); 84 G[x][y]=w; 85 G[y][x]=w; 86 } 87 best = prim(1); 88 int temp = SMST(); 89 if(temp == best) 90 printf("Not Unique!\n"); 91 else 92 printf("%d\n",best); 93 } 94 return 0; 95 }

CDOJ 1959

思路：這道題會出現(xiàn)重邊，用Kruskal算法處理起來比較方便。（用鄰接表方便，鄰接矩陣還要考慮同兩點之間的多條權(quán)值相同的邊。）

次小生成樹的權(quán)值如果等于最小生成樹的權(quán)值， 其替換邊只會是權(quán)值相同的邊，于是可以把權(quán)值相同邊放在一起考慮，分別判斷全部沒有合并時有多少可以合并（cnt1記錄的是可以加入集合的邊數(shù)），邊合并邊判斷有多少可以合并（cnt2記錄的是選中一條加入到集合），如果可選的大于構(gòu)成最小生成樹所需要的，那么就存在一種相同的邊權(quán)可以替換原來的，從而最小生成樹不唯一。

1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 const int N = 2e5+6; 5 struct Node 6 { 7 int u,v; 8 LL w; 9 }G[N]; 10 11 int n,m; 12 int f[2002]; 13 int find(int x) 14 { 15 return x==f[x]?x:f[x]=find(f[x]); 16 } 17 18 bool cmp(Node & a, Node & b) 19 { 20 return a.w<b.w; 21 } 22 23 void kruskal() 24 { 25 int cnt1=0; 26 int cnt2=0; 27 for(int i=1;i<=n;i++)f[i]=i; 28 sort(G,G+m,cmp); 29 for(int i=0;i<m;) 30 { 31 int j=i; 32 while(j<m&&G[j].w==G[i].w) 33 { 34 int u = find(G[j].u); 35 int v = find(G[j].v); 36 if(u!=v)cnt1++; 37 j++; 38 } 39 j=i; 40 while(j<m&&G[j].w==G[i].w) 41 { 42 int u = find(G[j].u); 43 int v = find(G[j].v); 44 if(u!=v){ 45 cnt2++; 46 f[u]=v; 47 } 48 j++; 49 } 50 i=j; 51 if(cnt1>cnt2)break; 52 } 53 if( cnt1 > cnt2 ){ 54 printf("zin\n"); 55 }else{ 56 printf("ogisosetsuna\n"); 57 } 58 } 59 60 int main() 61 { 62 int x,y; 63 LL w; 64 cin>>n>>m; 65 for(int i=0;i<m;i++) 66 { 67 cin>>x>>y>>w; 68 G[i].u=x; 69 G[i].v=y; 70 G[i].w=w; 71 } 72 kruskal(); 73 return 0; 74 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/demian/p/9188918.html

總結(jié)

以上是生活随笔為你收集整理的次小生成树(POJ1679/CDOJ1959)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。