題意：

求出最小生成樹中最大邊與最小邊差距的最小值。

分析：

排序，枚舉最小邊， 用最小邊構造最小生成樹， 沒法構造了就退出

1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <set> 9 #include <map> 10 #include <cstring> 11 #include <cmath> 12 #include <iomanip> 13 #define rep(i,a,b) for(int i = a; i < b;i++) 14 #define _rep(i,a,b) for(int i = a; i <= b;i++) 15 using namespace std; 16 const int inf = 1e9 + 7; 17 const int maxn = 100 + 7; 18 int n , m, cnt; 19 struct edge{ 20 int u, to , d; 21 bool operator < (const edge& a) const { 22 return d < a.d; 23 } 24 }G[maxn * maxn]; 25 int f[maxn]; 26 void init(){ 27 _rep(i,1,n) f[i] = i; 28 } 29 int get(int x){ 30 if(f[x] == x){ 31 return x; 32 }else{ 33 f[x] = get(f[x]); 34 return f[x]; 35 } 36 } 37 void merge(int a, int b){ 38 int t1 = get(a), t2 = get(b); 39 if(t1 != t2){ 40 f[t2] = t1; 41 } 42 } 43 int Kruskal(int st){ 44 int picked = 0; 45 int min_d = inf, max_d = -inf; 46 rep(i,st,m){ 47 int u = G[i].u, v = G[i].to, d = G[i].d; 48 if(get(u) != get(v)){ 49 merge(u,v); 50 picked++; 51 min_d = min(min_d, d), max_d = max(max_d , d); 52 } 53 if(picked == n - 1) return max_d - min_d;//已經構造出最小生成樹， 返回結果 54 } 55 return -1;//已經無法構造生成樹了， 結束枚舉 56 } 57 int main(){ 58 // freopen("1.txt","r", stdin); 59 while(cin >> n >> m && n){ 60 cnt = 0; 61 rep(i,0,m){ 62 int u , v , d; 63 cin >> u >> v >> d; 64 G[cnt].u = u , G[cnt].to = v, G[cnt].d = d; 65 cnt++; 66 } 67 sort(G, G + cnt); 68 int ans = inf; 69 for(int i = 0; i < m - n + 2; i++){ //由于至少要n-1條邊， 所以枚舉到m - n + 1 70 init(); 71 int t = Kruskal(i); 72 if(t != -1){ 73 ans = min(ans, t); 74 }else break; 75 } 76 printf("%d\n", ans == inf ? -1 : ans); 77 } 78 }

?

轉載于:https://www.cnblogs.com/Jadon97/p/8353880.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的POJ 3522 Slim Span (Kruskal枚举最小边)的全部內容，希望文章能夠幫你解決所遇到的問題。

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