UVA 10600 ACM Contest and Blackout ( 水題次小生成樹 )

UVa Online Judge
算出最小生成樹上每對最小瓶頸路徑就能 O( n * n ) 解決。
碎念：find() 函數忘了寫 return這個字= =

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

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;
        fa[x] = y; return true;
    }
} uf;

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;
int wei[MAXN][MAXN];
vector<Edge> G[MAXN];

struct Kruskal{
    int vis[MAXN], maxcost[MAXN][MAXN];
    vector<int> vis_node;
    void init(){
        uf.init( n );    
        sort( es, es + m );
        memset( vis, 0, sizeof(vis) );
        memset( maxcost, 0, sizeof(maxcost) );
        for(int i = 0; i <= n; ++i)
            G[i].clear();
        vis_node.clear();
    }
    void findBottleneckPath(int u, int fa){
        for(int x: vis_node)
            maxcost[ x ][ u ] = maxcost[ u ][ x ] = max( maxcost[ x ][ fa ], wei[ fa ][ u ] );
        vis_node.push_back( u );
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i].v;
            if( v == fa ) continue;
            findBottleneckPath( v, u );
        }
    }
    void solve(){
        int picked = 0, ans1 = 0;
        for(int i = 0; i < m; ++i){
            if( uf.unite( es[i].u, es[i].v ) ){
                vis[ i ] = 1;
                G[ es[i].u ].push_back( Edge( es[i].u, es[i].v, es[i].w ) );
                G[ es[i].v ].push_back( Edge( es[i].v, es[i].u, es[i].w ) );
                ans1 += es[i].w;
                if( ++picked == n - 1 ) break;
            }
        }
        assert( picked == n - 1 );
        findBottleneckPath( 1, -1 );
        int mindiff = INF;
        for(int i = 0; i < m; ++i) if( !vis[ i ] )
            mindiff = min( mindiff, es[i].w - maxcost[ es[i].u ][ es[i].v ] );
        int ans2 = ans1 + mindiff;
        printf("%d %d\n", ans1, ans2);
    }
} mst;

void solve(){
    mst.init();
    mst.solve();
}

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