CFR 437 D. The Child and Zoo ( Union Find )

Problem - D - Codeforces
顯然如果要從一個點到另一個點的路徑中最小權值最大，一定要沿著瓶頸生成樹走。圖裡的邊以兩端的最小值描述。很容易發現，越大的邊越有機會帶來影響，而某個邊有影響若且為若它是能將兩個無法相互到達的塊連通的邊裡邊權最大，並且這時候會影響的點對數有其兩個連通分量的總節點數乘積，乘上二得其排列。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;

int n, m;
int a[ MAXN ];

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

vector< Edge > G[ MAXN ];

struct UnionFind{
    int fa[ MAXN ];
    int sz[ MAXN ];
    void init( int _n ){
        for( int u = 1; u <= _n; ++u )
            fa[ u ] = u, sz[ u ] = 1;
    }
    int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite( int x, int y ){
        int g = find( x );
        int h = find( y );
        if( g == h ) return false;
        fa[ g ] = h;
        sz[ h ] += sz[ g ];
        return true;
    }
} uf;

void solve(){
    uf.init( n + 1 );
    sort( es, es + m );
    double ans = 0;
    for( int i = m - 1; i >= 0; --i ){
        int g = uf.find( es[ i ].u );
        int h = uf.find( es[ i ].v );
        if( g == h ) continue;
        ans += (double)es[ i ].w * uf.sz[ g ] * uf.sz[ h ] * 2;
        uf.unite( g, h );
    }
    printf("%.7lf\n", ans / ( (double)n * ( n - 1 ) ));
}

int main(){
    scanf("%d%d", &n, &m);
    for( int u = 1; u <= n; ++u )
        scanf("%d", a + u);
    for( int i = 0; i < m; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        int w = min( a[ u ], a[ v ] );
        G[ u ].push_back( es[ i ] = Edge( u, v, w ) );
        G[ v ].push_back( Edge( v, u, w ) );
    }
    solve();
    return 0;
}