一、题意

给出一个n（n<=100）结点的图，求苗条度（最大边减最小边的值）尽量小的生成树

二、解析

其实就是要求边权极差最小的生成树。
我们知道求最小生成树是用Kruskal算法，这里其实也是一样：我们枚举生成树的最小边E[l]，然后每次只从边权大于这条最小边边权的边中进行最小生成树的生成，这样就能得到这个生成树的最大边边权。这样枚举完后，我们就能得到边权极差最小的生成树了。

正确性证明：为什么最小生成树T就一定是这个最小边对应的苗条度最小的生成树呢？仔细回想一下Kruskal算法，最小生成树T是通过从小到大枚举边得到的，如果这个最小边对应的使得苗条度最小的最大边不在这个T中的话，那就是说存在一个由边权小于这个最大边的一组边构成的一棵更小的生成树，这就与T是最小生成树矛盾了。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100 + 5, INF = 1 << 30;
struct edge {
    int u, v, w;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator < (const edge& rhs) const {
        return w < rhs.w;
    }
};
vector<edge> E;
int n, m, Fa[maxn];

int find(int x) {
    return Fa[x] == x ? x : Fa[x] = find(Fa[x]);
}

int main() {
    while(cin >> n >> m && n) {
        E.clear();
        while(m --) {
            int u, v, w;
            cin >> u >> v >> w;
            E.push_back(edge(u, v, w));
        }
        sort(E.begin(), E.end());
        int ans = INF;
        for(int l = 0, r; l < E.size(); l ++) {
            for(int i = 1; i <= n; i ++) Fa[i] = i;
            int cnt = 0;
            for(int i = l; i < E.size(); i ++) {
                int u = find(E[i].u), v = find(E[i].v);
                if(u == v) continue;
                Fa[u] = v;
                if(++ cnt == n - 1) {
                    r = i;
                    break;
                }
            }
            if(cnt == n - 1) ans = min(ans, E[r].w - E[l].w);
        }
        cout << (ans == INF ? -1 : ans) << endl;
    }
}

四、归纳

  • 求边权极差最小的生成树模板： 
struct edge {
    int u, v, w;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator < (const edge& rhs) const {
        return w < rhs.w;
    }
};
vector<edge> E;
int n, m, Fa[maxn];

int find(int x) {
    return Fa[x] == x ? x : Fa[x] = find(Fa[x]);
}

int main() {
    ......
    sort(E.begin(), E.end());
    int ans = INF;
    for(int l = 0, r; l < E.size(); l ++) {  // 枚举最小边l，然后通过Kruskal求最大边r
        for(int i = 1; i <= n; i ++) Fa[i] = i;
        int cnt = 0;  // 用cnt记录加的边的条数，以此判断图是否连通完毕
        for(int i = l; i < E.size(); i ++) {
            int u = find(E[i].u), v = find(E[i].v);
            if(u == v) continue;
            Fa[u] = v;
            if(++ cnt == n - 1) {
                r = i;
                break;
            }
        }
        if(cnt == n - 1) ans = min(ans, E[r].w - E[l].w);
    }
    ......
}