UVA 1395 Slim Span ( 水題最小瓶頸生成樹 )

UVa Online Judge
先將邊以邊權排序後，枚舉以哪個邊為最小值，用最小瓶頸生成樹的算法算出最小的最大值。複雜度 O( n * m lg m )。據說這題有進階版
UVa Online Judge
UVA 12275 Sensor network - 0w1

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = MAXN * MAXN;
const int INF = 1e9;

struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
    bool operator < (const Edge &oth) const{
        return w < oth.w;
    }
} es[MAXM];

int n, m;
vector<Edge> G[MAXN];

struct UnionFind{
    int fa[MAXN];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[i] = i;
    }
    int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false; // no changes made
        fa[x] = y; return true;
    }
} uf;

struct Kruskal{ // es => 1 - idx
    void init(){
        for(int i = 0; i <= n; ++i)
            G[i].clear();
        uf.init( n );
    }
    int solve(int k){ // starts picking from the k'th smallest
        init();
        int picked = 0;
        sort( es, es + m );
        int cur;
        for(cur = k; cur < m; ++cur){
            if( uf.unite( es[ cur ].u, es[ cur ].v ) )
                ++picked;
            if( picked == n - 1 ) break;
        }
        if( picked < n - 1 ) return INF; // impossible
        return es[ cur ].w - es[ k ].w; // maxw - minw
    }
} mst;

void solve(){
    int ans = INF;
    for(int i = 0; i < m; ++i)
        ans = min( ans, mst.solve( i ) );
    if( ans == INF ) puts("-1");
    else printf("%d\n", ans);
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 && n + m ){
        for(int i = 0; i < m; ++i)
            scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].w);
        solve();
    }
    return 0;
}