HDU 4081 MST

這道題在LRJ的書上看到，今天回過頭來繼續看這題，發現很多東西都已經明白了。 題意：有N個城市，每個城市有一個坐標和人口。 現在要建一些邊使得他們都聯通，花費就是這些邊的長度，然後有一條邊可以免費。問免費一條邊之後，使得免費的該條邊的兩個城市的人口/剩下來的邊的長度 ，這個比值最大。 思路：首先做一遍MST，求出MST之後，我們枚舉每條邊，看這條邊是否可以刪除，也就是免費。 那麼刪除一條邊之後對MST有什麼影響呢。 首先我們假設免費(刪除)了一條邊a -> b ,權值是c 。假設這條邊是MST上的邊，那麼我們只能刪除這條邊 。 假設這條邊不是MST上的邊，那麼我們可以刪除a -> b權值最大的一條邊，因為我們是要使得剩下來的長度最小。  

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <string>  
#include <stack>  
#include <set>  
#include <map>  
#include <queue>  
#include <algorithm>  
#define ll long long  
#define inf 1<<30  
#define PI acos(-1.0)  
#define mem(a , b) memset(a , b ,sizeof(a))  
using namespace std ;  
  
struct kdq {  
    int s , e  ;  
    double l ;  
    bool operator < (const kdq & fk)const {  
        return l > fk.l ;  
    }  
} ;  
inline void RD(int &ret) {  
    char c;  
    int flag = 1 ;  
    do {  
        c = getchar();  
        if(c == '-')flag = -1 ;  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
    ret *= flag ;  
}  
#define N 1111  
double ed[N][N] , edM[N][N] ;  
int x[N] , y[N], pop[N] ;  
int n ;  
double mst = 0 ;  
double getdis(int i ,int j) {  
    return sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j])) ;  
}  
void init() {  
    cin >> n ;  
    for (int i = 1; i <= n ; i ++ ) {  
        RD(x[i]) ; RD(y[i]) ; RD(pop[i]) ;  
    }  
    for (int i = 1 ; i <= n ; i ++ ) {  
        for (int j = 1;  j <= n ; j ++ ) {  
            if(i == j)ed[i][j] = 0 ;  
            else ed[i][j] = getdis(i , j) ;  
        }  
    }  
    mst = 0 ;  
}  
double dis[N] ;  
int vis[N] ;  
bool ok[N][N] ;  
vector<int>E[N] ;  
  
void prim() {  
    priority_queue<kdq>qe ;  
    for (int i = 1 ; i <= n ; i ++ ) {  
        dis[i] = ed[1][i] ;  
        E[i].clear() ;  
    }  
    mem(vis ,0) ;  
    mem(ok ,0) ;  
    for (int i = 1 ; i <= n ; i ++ ) {  
        qe.push((kdq) {1 , i , ed[1][i]}) ;  
    }  
    dis[1] = 0 , vis[1] = 1 ;  
    while(!qe.empty()) {  
        kdq tp = qe.top() ;  
        qe.pop() ;  
        if(vis[tp.e])continue ;  
        mst += ed[tp.s][tp.e] ;  
        vis[tp.e] = 1 ;  
        ok[tp.s][tp.e] = ok[tp.e][tp.s] = 1 ;  
        E[tp.s].push_back(tp.e) ;  
        E[tp.e].push_back(tp.s) ;  
        for (int i = 1 ; i <= n ; i ++ ) {  
            if(!vis[i] && dis[i] > ed[tp.e][i]) {  
                dis[i] = ed[tp.e][i] ;  
                qe.push((kdq){tp.e , i , ed[tp.e][i]}) ;  
            }  
        }  
    }  
}  
void dfs(int root ,int fa ,int now ,double MAX) {  
    edM[root][now] = MAX ;  
    int sz = E[now].size() ;  
    for (int i = 0 ; i < sz ; i ++ ) {  
        int e = E[now][i] ;  
        if(e == fa)continue ;  
        dfs(root , now , e , max(MAX  , ed[now][e])) ;  
    }  
}  
void solve() {  
    init() ;  
    prim() ;  
    for (int i = 1 ; i <= n ; i ++ ) {  
        dfs(i , -1 , i , 0) ;  
    }  
    double ans = -1 ;  
    for (int i = 1 ; i <= n ; i ++ ) {  
        for (int j = 1 ; j < i ; j ++ ) {  
            if(ok[i][j])  
                ans = max(ans , (pop[i] + pop[j]) * 1.0 / (mst - ed[i][j])) ;  
            else  
                ans = max(ans , (pop[i] + pop[j]) * 1.0 / (mst - edM[i][j])) ;  
        }  
    }  
    printf("%.2f\n",ans) ;  
}  
int main() {  
    int _ ;cin >> _ ;while(_ -- )solve() ;  
    return 0;  
}