模板題，學(xué)習(xí)一下最小生成樹的Kruskal算法

?

對于一個連通網(wǎng)（連通帶權(quán)圖，假定每條邊上的權(quán)均為大于零的實數(shù)）來說，每棵樹的權(quán)（即樹中所有邊的權(quán)值總和）也可能不同

具有權(quán)最小的生成樹稱為最小生成樹

生成樹：

• 無向連通圖的邊的集合
• 無回路
• 連接所有的點

最小：

• 所有邊的權(quán)值之和最小

n個頂點的樹有n-1條邊

時間復(fù)雜度：O(ElogE)

?

對于稀疏圖來說

按所給的邊的權(quán)值從小到大排序，如果該邊不與已經(jīng)選的邊形成環(huán)就選擇它

這里用并查集來實現(xiàn)

第i條邊的端點放在u、v數(shù)組中，權(quán)值保存在w中

這里用的是間接排序，也就是排的是每條邊的序號，放在rank數(shù)組中

?

下面是兩道模板題：

HDU 1863 暢通工程

1 //#define LOCAL 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 5000; 8 int u[maxn], v[maxn], w[maxn], parent[maxn], rank[maxn]; 9 int m, n; 10 11 bool cmp(const int i, const int j) 12 { 13 return (w[i] < w[j]); 14 } 15 16 int GetParent(int a) 17 { 18 return parent[a] == a ? a : parent[a] = GetParent(parent[a]); 19 } 20 21 int kruskal(void) 22 { 23 int cnt = 0, weight = 0; 24 for(int i = 0; i < m; ++i) 25 { 26 int edge = rank[i]; 27 int x = GetParent(u[edge]); 28 int y = GetParent(v[edge]); 29 if(x != y) 30 { 31 weight += w[edge]; 32 ++cnt; 33 parent[x] = y; 34 } 35 } 36 if(cnt < n - 1) weight = 0; 37 return weight; 38 } 39 40 int main(void) 41 { 42 #ifdef LOCAL 43 freopen("1863in.txt", "r", stdin); 44 #endif 45 46 47 while(scanf("%d%d", &m, &n) == 2 && m) 48 { 49 for(int i = 0; i < m; ++i) 50 scanf("%d%d%d", &u[i], &v[i], &w[i]); 51 for(int i = 0; i < n; ++i) parent[i] = i; 52 for(int i = 0; i < m; ++i) rank[i] = i; 53 sort(rank, rank + m, cmp); 54 int ans = kruskal(); 55 if(ans) 56 printf("%d\n", ans); 57 else 58 printf("?\n"); 59 } 60 return 0; 61 } 代碼君一

?

POJ 1861 Network

感覺這道題略坑啊，它并沒有說是多組輸入啊，而且輸出的第一個數(shù)是邊里面的最大權(quán)值啊，數(shù)組開了1000多開小了啊，還有各種小錯誤啊。Orz

好吧，這些都是我的錯誤，上來就套模板，沒有好好讀題

1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1000 + 10; 9 int v[maxn], u[maxn], r[maxn], p[maxn], w[maxn], path[maxn]; 10 int n, m, cnt, ans; 11 12 int Find(int a) 13 { 14 return p[a] == a ? a : p[a] = Find(p[a]); 15 } 16 17 bool cmp(const int i, const int j) 18 { 19 return (w[i] < w[j]); 20 } 21 22 void Kruskal(void) 23 { 24 cnt = 0, ans = -1; 25 for(int i = 0; i < m; ++i) 26 { 27 int edge = r[i]; 28 int x = Find(u[edge]); 29 int y = Find(v[edge]); 30 if(x != y) 31 { 32 ans = max(ans, w[edge]); 33 p[x] = y; 34 path[cnt++] = i; 35 } 36 } 37 } 38 39 void OutPut(void) 40 { 41 printf("%d\n%d\n", ans, cnt); 42 for(int i = 0; i < cnt; ++i) 43 printf("%d %d\n", u[r[path[i]]], v[r[path[i]]]); 44 } 45 46 int main(void) 47 { 48 #ifdef LOCAL 49 freopen("1861in.txt", "r", stdin); 50 #endif 51 52 while(scanf("%d%d", &n, &m) == 2) 53 { 54 for(int i = 0; i < m; ++i) 55 scanf("%d%d%d", &u[i], &v[i], &w[i]); 56 for(int i = 0; i < n; ++i) p[i] = i; 57 for(int i = 0; i < m; ++i) r[i] = i; 58 sort(r, r + m, cmp); 59 Kruskal(); 60 OutPut(); 61 } 62 63 return 0; 64 } 代碼君二

?

POJ 2560 Freckles

題意：給出n個點的坐標，求最小生成樹的長度。奇怪的是G++沒過，C++卻過了

1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 9 const int maxn = 5000 + 10; 10 struct Node 11 { 12 double x, y; 13 }pos[maxn]; 14 15 int u[maxn], v[maxn], r[maxn], p[maxn]; 16 double w[maxn]; 17 18 bool cmp(const int i, const int j) 19 { 20 return (w[i] < w[j]); 21 } 22 23 int Find(int a) 24 { 25 return p[a] == a ? a : p[a] = Find(p[a]); 26 } 27 28 double Kruskal(int cnt) 29 { 30 double ans = 0.0; 31 for(int i = 0; i < cnt; ++i) 32 { 33 int edge = r[i]; 34 int x = Find(u[edge]); 35 int y = Find(v[edge]); 36 if(x != y) 37 { 38 ans += w[edge]; 39 p[x] = y; 40 } 41 } 42 return ans; 43 } 44 45 int main(void) 46 { 47 #ifdef LOCAL 48 freopen("2560in.txt", "r", stdin); 49 #endif 50 51 int n, cnt; 52 while(scanf("%d", &n) == 1) 53 { 54 for(int i = 0; i < n; ++i) p[i] = i; 55 for(int i = 0; i < n; ++i) 56 scanf("%lf %lf", &pos[i].x, &pos[i].y); 57 cnt = 0; 58 for(int i = 1; i < n; ++i) 59 for(int j = 0; j < i; ++j) 60 { 61 u[cnt] = i; 62 v[cnt] = j; 63 r[cnt] = cnt; 64 w[cnt++] = sqrt((pos[i].x-pos[j].x)*(pos[i].x-pos[j].x) + (pos[i].y-pos[j].y)*(pos[i].y-pos[j].y)); 65 } 66 sort(r, r + cnt, cmp); 67 printf("%.2lf\n", Kruskal(cnt)); 68 } 69 70 return 0; 71 } 代碼君三

?

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

總結(jié)

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

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