UVA 10369 Arctic Network ( 水題最小瓶頸生成樹 )

UVa Online Judge
取到排序後第 p - s + 1個最小的就可以了。

#include <bits/stdc++.h>
using namespace std;
const int MAXS = 100 + 2;
const int MAXP = 500 + 2;
const int MAXM = MAXP * MAXP / 2;

int n, m;

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

struct UnionFind{
    int fa[MAXP];
    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;
        fa[x] = y; return true;
    }
} uf;

int s, p;
int x[MAXP], y[MAXP];

struct Kruskal{
    void init(){
        uf.init( p );
        sort( es, es + m );
    }
    double solve(){
        int picked = 0;
        double res;
        for(int i = 0; i < m; ++i){
            if( uf.unite( es[i].u, es[i].v ) ){
                res = es[i].w;
                if( ++picked == p - s ) break;
            }
        }
        assert( picked == p - s );
        return res;
    }
} mst;

double euDis(int a, int b){
    double sqrx = (double)( x[ a ] - x[ b ] ) * ( x[ a ] - x[ b ] );
    double sqry = (double)( y[ a ] - y[ b ] ) * ( y[ a ] - y[ b ] );
    return sqrt( sqrx + sqry );
}

void makeEdge(){
    m = 0;
    for(int i = 0; i < p; ++i)
        for(int j = i + 1; j < p; ++j)
            es[ m++ ] = Edge( i, j, euDis( i, j ) );
}

void solve(){
    makeEdge();
    mst.init();
    printf("%.2lf\n", mst.solve());
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d%d", &s, &p);
        for(int i = 0; i < p; ++i)
            scanf("%d%d", &x[i], &y[i]);
        solve();
    }
    return 0;
}