HDU - 4081 Qin Shi Huang 's National Road System (최소 생 성 트 리)

오늘 경기 에서 AC 의 최소 생 성 트 리 문제 로 많은 것 을 배 웠 다. 
트 리 를 최소 로 만 드 는 템 플 릿 은 간단 합 니 다. 가장 간결 하고 쓰기 좋 은 것 은 lrj 자줏빛 책의 코드 입 니 다.가속 알고리즘 을 이용 하여 집합 하 다.
이 문제 의 차이 점 은 임의의 길 을 선택 하여 '마법' 도 로 를 만 든 다음 에 다른 길의 가중치 의 합 은 가장 작은 작은 작은 생 성 나무 이 고 마법 도로 의 양 끝 점 치 와 다른 경로 의 길이 의 합 을 나 누 는 최대 치 를 구 하 는 것 이다.
분명히 이 문제 의 난점 은 두 개의 단점 을 매 거 한 후에 어떻게 작은 생 성 트 리 의 가중치 의 합 을 신속하게 구 하 느 냐 에 있다. 두 점 을 매 거 한 후의 복잡 도 는 이미 O (n ^ 2) 이기 때문에 빠 른 방법 을 생각해 내야 한다.
자서 의 예제 uva 1151 (전송 문) 의 깨 우 침 을 받 아 그 문제 와 약간의 차이 가 있 지만 사상 은 같다.우 리 는 임의의 두 점 을 선택 한 후에 한 과목 의 최소 생 성 트 리 를 만 들 려 면 나머지 한 쪽 은 최초의 최소 생 성 트 리 에서 찾 아야 한다.문 제 는 양쪽 을 매 거 한 뒤 어느 쪽 을 삭제 해 야 할 지 어떻게 알 느 냐 하 는 것 이다.  정 답 은 최초의 최소 생 성 트 리 에서 이 두 점 의 경로 에서 가중치 가 가장 큰 변 을 삭제 하 는 것 입 니 다. 。 이렇게 하면 작은 생 성 나 무 를 한 그루 낳 을 수 있다.
문 제 는 최소 생 성 트 리 의 임 의 두 가지 경로 중 가장 큰 가중치 변 을 어떻게 빨리 찾 느 냐 하 는 것 이다.(나무 한 그루 의 임의의 두 점 사이 에 유일한 경로 가 있다).
간단 합 니 다. 재 귀적 으로 검색 하면 됩 니 다. ，  O (n ^ 2) 의 시간 이 필요 합 니 다.그래서 총 시간 은 O (n ^ 2) 입 니 다.
그러나 경기 할 때 TLE 가 되 었 습 니 다. 그래서 우 리 는 무 작위 로 10 개의 데 이 터 를 생 성하 고 달 렸 습 니 다. 2 초 가 넘 게 걸 렸 습 니 다. 우 리 는 코드 일 부 를 계속 주석 을 달 아 놓 고 시간 이 어디 에 소모 되 었 는 지 보 았 습 니 다. 그 결과 주 고 정렬 하 는 데 소모 되 었 습 니 다.
내 가 처음 전 하 는 함수, 슬기 로 운 동료 들 이 구조 체 내부 에서 연산 자 보다 작 게 정의 하 는 것 으로 바 꿔 주 었 더 니 몇 배 나 빨 라 졌 다.
자세 한 참조 코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 1000 + 5;
int T,n,m,p[maxn],cnt,vis[maxn];
vector<int> g[maxn];
double b[maxn][maxn],gg[maxn][maxn];
struct node {
    double x,y,c;
}a[maxn];
struct edge{
    int a,b;
    double dist;
    bool operator < (const edge &e) const {
        return dist < e.dist;
    }
}e[maxn*maxn];
bool cmp(edge a,edge b) {
    return a.dist < b.dist;
}
int findd(int x) { return p[x] == x ? x : p[x] = findd(p[x]); }
void dfs(int root,int cur) {
    vis[cur] = 1;
    for(int i=0;i<g[cur].size();i++) {
        int v = g[cur][i];
        if(!vis[v]) {
            gg[root][v] = max(b[cur][v],gg[root][cur]);
            dfs(root,v);
        }
    }

}
double solve() {
    for(int i=1;i<=n;i++) p[i] = i , g[i].clear();
    sort(e,e+cnt);
    int res = 0;
    double sum = 0;
    for(int i=0;i<cnt;i++) {
        int x = findd(e[i].a) , y = findd(e[i].b);
        if(x != y) {
            p[x] = y;
            sum += e[i].dist;
            g[e[i].a].push_back(e[i].b);
            g[e[i].b].push_back(e[i].a);
            b[e[i].a][e[i].b] = b[e[i].b][e[i].a] = e[i].dist;
        }
    }
    for(int i=1;i<=n;i++) {
        memset(vis,0,sizeof(vis));
        dfs(i,i);
    }
    double ans = 0;
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            double v = sum - gg[i][j];
            v = (a[i].c + a[j].c) /v;
            ans = max(ans,v);
        }
    }
    return ans;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);    cnt = 0;
        for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].c);
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++) {
                double d = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
                e[cnt].a = i; e[cnt].b = j; e[cnt++].dist = d;
            }
        }
        printf("%.2f
",solve());
    }
    return 0;
}