UVA 1494 Qin Shi Huang's National Road System ( 次小生成樹 )

UVa Online Judge
很明顯是一個類似次小生成樹的問題，因為只刪除一個邊，我們考慮一一枚舉要刪除的邊互相比較。將每個點對的最小瓶頸路徑預處理 O( n * n )，檢查刪除後的權值總和就能達到 O( 1 )。總複雜度 O( m lg m + n * n )。關於最小瓶頸路徑可以看這則
生成樹相關問題 -- 訓練指南 - 0w1

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;

int n, m;
int x[MAXN], y[MAXN], p[MAXN];

struct Edge{
    int u, v;
    double c;
    bool operator < (const Edge &oth) const{
        return c < oth.c;
    }
} es[MAXN * MAXN];

vector<Edge> G[MAXN];

int head[MAXN];
int find(int x){ return x == head[x] ? x : head[x] = find( head[x] ); }
bool unite(int a, int b){
    int x = find( a ), y = find( b );
    if( x == y ) return false;
    head[ x ] = y;
    return true;
}

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

double kruskal(){
    m = 0;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            es[ m++ ] = (Edge){ i, j, euDis( i, j ) };
    sort( es, es + m );
    for(int i = 0; i < n; ++i) head[i] = i, G[i].clear();
    double ans = 0.0;
    int edge_cnt = 0;
    for(int i = 0; i < m; ++i){
        int u = es[i].u, v = es[i].v;
        double c = es[i].c;
        if( unite( u, v ) ){
            G[u].push_back( (Edge){ u, v, c } );
            G[v].push_back( (Edge){ v, u, c } );
            ans += c;
            if( ++edge_cnt == n - 1 ) break;
        }
    }
    return ans;
}

double maxcost[MAXN][MAXN]; // maximum cost in route between u <-> v
vector<int> visited;
void dfs(int v, int u, double wuv){ // from u, now on v, cost of u <-> v is wuv
    for(int x: visited)
        maxcost[x][v] = maxcost[v][x] = max( maxcost[x][u], wuv );
    visited.push_back( v );
    for(int i = 0; i < G[v].size(); ++i){
        int nv = G[v][i].v;
        if( nv == u ) continue;
        dfs( nv, v, G[v][i].c );
    }
}
void findBottleneckPath(){
    memset( maxcost, 0, sizeof(maxcost) );
    visited.clear();
    dfs( 0, -1, 0.0 );
}

void solve(){
    double mstv = kruskal();
    findBottleneckPath();
    double ans = -1;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            ans = max( ans, ( p[i] + p[j] ) / ( mstv - maxcost[i][j] ) );
    printf("%.2lf\n", ans);
}

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