hdu4081

hdu4081

题意

给出n个点坐标，每个点有权值，要求得到一颗生成树，且其中有一条道路修建不需要花费，但是要求这条道路所连接的两点的权值之和除以剩下所有道路的距离花费最大。

分析

首先求最小生成树，然后枚举所有的边，即去掉这条边后，在得到的两个连通图中分别找最大权值的点，计算最优比率。

code

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;

const double INF = 1e15;

struct node {

    int x, y, w;

}p[MAXN];

int n;

double map[MAXN][MAXN];

double dist(int x1, int y1, int x2, int y2) {

    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

double dis[MAXN];

int vis[MAXN], pre[MAXN];

double prime() {

    double sum = 0;

    memset(pre, 0, sizeof pre);

    memset(vis, 0, sizeof vis);

    for(int i = 1; i <= n; i++) {

        dis[i] = INF;

    }

    dis[1] = 0;

    for(int i = 0; i < n; i++) {

        double MIN = INF;

        int k;

        for(int j = 1; j <= n; j++) {

            if(!vis[j] && dis[j] < MIN) MIN = dis[k = j];

        }

        vis[k] = 1;

        sum += MIN;

        for(int j = 1; j <= n; j++) {

            if(!vis[j] && dis[j] > map[k][j]) {

                dis[j] = map[k][j];

                pre[j] = k;

            }

        }

    }

    return sum;

}

void dfs(int x) {

    vis[x] = 1;

    for(int i = 1; i <= n; i++) {

        if(!vis[i] && pre[i] == x) dfs(i);

    }

}

void solve() {

    double ans = 0;

    double sum = prime();

    for(int i = 1; i <= n; i++) {

        if(!pre[i]) continue;

        double temp = sum - map[i][pre[i]];

        int a = 0, b = 0;

        memset(vis, 0, sizeof vis);

        dfs(i);

        for(int j = 1; j <= n; j++) {

            if(vis[j]) a = max(a, p[j].w);

            else b = max(b, p[j].w);

        }

        ans = max(ans, (a + b) / temp);

    }

    printf("%.2f\n", ans);

}

int main() {

    int T;

    for(cin >> T; T--;) {

        cin >> n;

        for(int i = 1; i <= n; i++) {

            cin >> p[i].x >> p[i].y >> p[i].w;

            for(int j = 1; j <= i; j++) {

                map[j][i] = map[i][j] = dist(p[i].x, p[i].y, p[j].x, p[j].y);

            }

        }

        solve();

    }

    return 0;

}