題目大意：

　　給n個節點，m條邊，問最小生成樹，次小生成樹？

　　ps：以前做次小生成樹的時候估計沒有掌握牢固，這次wa的好辛苦喲。

1 #include <cmath> 2 #include <queue> 3 #include <string> 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 10 const int maxn = 100; 11 const int INF = 0x3f3f3f3f; 12 const double Exp = 1e-10; 13 14 int cost[maxn+10][maxn+10], lowc[maxn+10], vis[maxn+10]; 15 int Max[maxn+10][maxn+10], used[maxn+10][maxn+10], pre[maxn+10]; 16 int n; 17 void init () 18 { 19 for (int i=1; i<=n; i++) 20 for (int j=1; j<=n; j++) 21 if (i == j) 22 cost[i][j] = 0; 23 else 24 cost[i][j] = INF; 25 } 26 int prim () 27 { 28 int i, j, sum = 0; 29 memset (Max, 0, sizeof(Max)); 30 memset (used, 0, sizeof(used)); 31 memset (vis, 0, sizeof(vis)); 32 vis[1] = 1; 33 for (i=1; i<=n; i++) 34 { 35 lowc[i] = cost[1][i]; 36 pre[i] = 1; 37 } 38 for (i=1; i<n; i++) 39 { 40 int p, mini = INF; 41 for (j=1; j<=n; j++) 42 if (!vis[j] && mini > lowc[j]) 43 { 44 p = j; 45 mini = lowc[j]; 46 } 47 vis[p] = 1; 48 sum += mini; 49 used[pre[p]][p] = used[p][pre[p]] = 1; 50 for (j=1; j<=n; j++) 51 {//這一點的錯誤wa的好苦 52 if (vis[j] && j != p)//p!=j一定要有，否則Max[i][i]的距離就可能會不等于零，影響后面的計算過程 53 Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]); 54 if (!vis[j] && lowc[j] > cost[p][j]) 55 { 56 lowc[j] = cost[p][j]; 57 pre[j] = p; 58 } 59 } 60 } 61 return sum; 62 } 63 int smst (int sum) 64 { 65 int i, j, mini = INF; 66 for (i=1; i<=n; i++) 67 for (j=i+1; j<=n; j++) 68 if (cost[i][j] != INF && !used[i][j]) 69 mini = min (mini, sum + cost[i][j] - Max[i][j]); 70 return mini; 71 } 72 int main () 73 { 74 int t, m; 75 scanf ("%d", &t); 76 while (t --) 77 { 78 scanf ("%d %d", &n, &m); 79 init (); 80 while (m --) 81 { 82 int a, b, c; 83 scanf ("%d %d %d", &a, &b, &c); 84 cost[a][b] = cost[b][a] = c; 85 } 86 int num1, num2; 87 num1 = prim (); 88 num2 = smst (num1); 89 printf ("%d %d\n", num1, num2); 90 } 91 return 0; 92 }

?

轉載于:https://www.cnblogs.com/alihenaixiao/p/4549538.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的UVA 10600 ACM Contest and Blackout (次小生成树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。