AOJ Slim Span

解法

まず全域木の中で、重みが最小となる辺を固定する。その重み以上辺のみを使って、$Kruskal$法によって最小全域木を作り、その時の$Slimness$を求め、その最小値をとる。
辺はあらかじめ重みで昇順にソートしておけば、順番に辺を選んでいくだけでよいことになる。計算量は一応$\ O(m^2)\ $。

実装

#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

struct edge { 
        int a, b, c; 
        edge(int a, int b, int c) : a(a), b(b), c(c) { }
};

static const int INF = 0x3f3f3f3f;
                                 
int main() {
        int n, m;
        while (cin >> n >> m && n) {
                vector<edge> es;
                for (int i = 0; i < m; i ++) {
                        int a, b, c;
                        cin >> a >> b >> c;
                        a --, b --;
                        edge e(a, b, c);
                        es.push_back(e);
                }
                sort(all(es), [](const edge &a, const edge &b) {
                        return a.c < b.c;
                });
                int ans = INF;
                for (int i = 0; i < m; i ++) {
                        int cnt = 0;
                        UnionFind uf(n);
                        for (int j = i; j < m; j ++) {
                                if (uf.same(es[j].a, es[j].b)) continue;
                                uf.unite(es[j].a, es[j].b);
                                cnt ++;
                                if (cnt == n - 1) {
                                        ans = min(ans, es[j].c - es[i].c);
                                        break;
                                }
                        }
                }
                if (ans == INF) ans = -1;
                cout << ans << endl;
        }
        return 0;
}