感謝這篇文章
本文對其代碼，進行一些解釋。

這道題的題意很明了。求最大邊與最小邊差值最小的生成樹

首先，把所有的生成樹都求出來是不可能的，所以，必須用別的方法。

在學習次小生成樹的過程中，知道了一個最小生成樹的性質(zhì)， 一個圖的最小生成樹不一定是唯一的，但是組成這些最小生成樹的各個邊的權(quán)值一定都是一一對應相同的。不會出現(xiàn)這種一個樹上有兩個邊權(quán)值a+b等于另外一顆樹上兩個邊c+d，然后這兩個樹都是最小生成樹的情況。

對于本題來講，上面那個性質(zhì)就說明了一個圖的最小生成樹上的最小邊的權(quán)值和最大邊的權(quán)值是固定不變的。那么當使用克魯斯卡爾算法時，第一次加入的必然是邊權(quán)最小的邊，由于克魯斯卡爾算法的正確性已經(jīng)得到驗證過，那么此邊的權(quán)值必然就是最小生成樹的最小邊權(quán)值了，當最小邊的權(quán)值固定時，最小生成樹的最大邊的權(quán)值也“命中注定”是固定的，在最小邊權(quán)值固定的情況下，其他的生成樹的最大邊必然也是大于等于最小生成樹的最大邊，否則就不滿足我們上文提到的性質(zhì)，這就是“當生成樹的最小邊確定時，最小生成樹的最大邊的權(quán)值是所有生成樹中最小的”。從而，我們得到了一個本題的解法。 枚舉最小邊，然后求最小生成樹，更新最優(yōu)解。

代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define pi pair<int,int> #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3fconst int N = 1e4 + 10;// e[i] 表示第i條邊的信息（連接u和v，權(quán)值為w） struct edge {int u, v, w;edge(int u1=0,int v1=0,int w1=0):u(u1),v(v1),w(w1){}bool operator <(const edge e1){return this->w < e1.w;} }e[N];bool vis[N]; int n, m; int fa[N];void init() {for (int i = 0; i <= n; ++i)fa[i] = i; }int find(int x) {if (fa[x] == x)return x;elsereturn fa[x] = find(fa[x]); }void join(int x,int y) {x = find(x);y = find(y);if (x != y)fa[x] = fa[y]; }bool same(int a, int b) {return find(a) == find(b); }int Kruskal() {sort(e + 1, e + m+1);int flag = 0, ans = INF;//枚舉每一個最小邊，for (int i = 1; i <= m; ++i){init();//并查集初始化int cnt = 1;//以該邊來構(gòu)建最小生成樹的最大邊權(quán)，和最小邊權(quán)int hight = e[i].w, low = e[i].w;//加入這條邊join(e[i].u, e[i].v);//從該邊后面的邊選邊組成最小生成樹for (int j = i+1 ; j <= m; ++j){if (!same(e[j].u, e[j].v)){join(e[j].u, e[j].v);hight = max(hight, e[j].w);cnt++;}if (cnt == n - 1)break;}if (cnt == n - 1)//如果能構(gòu)成了最小生成樹{flag = 1;//更新ans = min(ans, hight - low);}}if (!flag)return -1;elsereturn ans; }int main() {while (~scanf_s("%d%d", &n, &m)&&(n||m)){mst(e, 0);for (int i = 1; i <= m; ++i)scanf_s("%d%d%d", &e[i].u, &e[i].v, &e[i].w);printf("%d\n", Kruskal());}return 0; }

總結(jié)

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

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