POJ 3522 Slim Span 生成樹

http://poj.org/problem?id=3522

求使最大邊權差最小的生成樹。

分析一下問題性質。最大邊權差最小？差即是最大邊權減去最小邊權，要使答案區間長度最小，一種可能的方法便是掃描線，即枚舉區間的一個端點，快速判斷另一個端點的最優位置。回到本題，kruskal的性質很明了，由于一直是從小到大依次貪心地枚舉邊，是以kruskal運作完成即滿足最大邊盡可能小的要求。是以區間另一端點的最優位置就可以求得，本題解決。

#include <cstdio>
#include <algorithm>
using namespace std;
struct Edge { int u, v, w; } e[];
bool operator<(const Edge &a, const Edge &b) { return a.w < b.w; }
int fa[];
int find(int i) { return fa[i] == i ? i : fa[i] = find(fa[i]); }
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF && (n || m)) {
        for (int i = ; i < m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        sort(e, e + m);
        int ans = ;
        for (int i = ; i < m; ++i) {
            for (int j = ; j <= n; ++j) fa[j] = j;
            int sets = n;
            for (int j = i; j < m; ++j)
                if (find(e[j].u) != find(e[j].v)) {
                    --sets; fa[find(e[j].u)] = find(e[j].v);
                    if (sets == ) {
                        ans = min(ans, e[j].w - e[i].w);
                        break;
                    }
                }
        }
        printf("%d\n", ans ==  ? - : ans);
    }
    return ;
}