传送门

昨天第一次跟两个妹子一起打……真特么那个紧张啊 人生赢家请闭嘴

这题应该是属于我的题目但到最后还是没有A掉的,如果到了现场赛,这样怕是要打铁了……

题意:
给你n个点与其权值,求一棵生成树,满足 A/B 的值最大
其中,A = 生成树中任选的一条边所连接的两个点的权值和,B = 生成树总长 - 你选中的边的长度

思路:
为满足 A/B 最大,则必须使得 A 尽量大 ,B 尽量小。
假设选中的边已经确定,那么剩下的 n-2 条边肯定在最小生成树中(这是显然的)。那么,其实我们可以先生成一棵最小生成树,然后枚举他的边,将它暂时删除。
在一棵树中删除一条边,将形成两棵子树(这里把点也考虑上),为使重新构成生成树,我们必须在两棵子树之间重新构造一条边。为使 A 最大,我们只要两棵子树上分别寻在权值最大的点即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1005;
const double eps = 1e-6;

int n;
bool vis[maxn];

struct node {
    double x, y;
    int w;
} nodes[maxn];

struct edge {
    int from;
    int to;
    double dis;
    edge(int x = 0, int y = 0, int z = 0)
    {
        from = x;
        to = y;
        dis = z;
    }
    bool operator<(const edge& a) const
    {
        return dis > a.dis + eps;
    }
} edges[maxn][maxn];

vector<int> graph[maxn];
priority_queue<edge> que;

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i <= n; i++)
        graph[i].clear();
    memset(vis, false, sizeof vis);
}

double cal(node& a, node& b)
{
    return sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}

double getSum(int cur, int pre, double sum)
{
    sum = max(sum, (double)(nodes[cur].w));
    int sz = graph[cur].size();
    for (int i = 0; i < sz; i++) {
        if (graph[cur][i] != pre)
            sum = max(sum, getSum(graph[cur][i], cur, sum));
    }
    return sum;
}

double pri_prime(int st)
{
    edge tmp;
    int v;
    double ans = 0;
    for (int i = 1; i <= n; i++)
        que.push(edges[st][i]);
    vis[st] = true;
    for (int i = 0; i < n - 1; i++) {
        do {
            tmp = que.top();
            que.pop();
        } while (vis[tmp.to]);
        v = tmp.to;
        vis[v] = true;
        ans += tmp.dis;
        graph[tmp.from].push_back(tmp.to);
        graph[tmp.to].push_back(tmp.from);
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                tmp.from = v;
                tmp.to = i;
                tmp.dis = edges[v][i].dis;
                que.push(tmp);
            }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    double sum;
    cin >> T;
    while (T--) {
        cin >> n;
        init();
        for (int i = 1; i <= n; i++)
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].w;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++) {
                edges[i][j].from = i;
                edges[i][j].to = j;
                edges[j][i].from = j;
                edges[j][i].to = i;
                edges[j][i].dis = edges[i][j].dis = cal(nodes[i], nodes[j]);
            }
        double final_len = pri_prime(1), ans = 0;
        for (int i = 1; i <= n; i++) {
            int sz = graph[i].size();
            for (int j = 0; j < sz; j++) {
                int v = graph[i][j];
                sum = getSum(v, i, 0) + getSum(i, v, 0);
                ans = max(ans, sum / (final_len - edges[i][v].dis));
            }
        }
        printf("%.2f\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最小生成树

HDU 4408 Minimum Spanning Tree

真是不容易啊…… 最小生成树计数,虽然说觉得以后已经基本不会考到了,但 Read more…

最小生成树

BZOJ 1016 [JSOI2008]最小生成树计数

bzoj 第一题,矩阵树算法写起来炒鸡烦,就先去写了一发暴力的…… 说 Read more…

最小生成树

关于最小生成树计数算法的粗浅证明

问题描述 最小生成树计数问题是给定一个无向带权图,问你能生成最小生成树 Read more…