题目大意：

有n个城市，秦始皇要修用n-1条路把它们连起来，要求从任一点出发，都可以到达其它的任意点。秦始皇希望这所有n-1条路长度之和最短。然后徐福突然有冒出来，说是他有魔法，可以不用人力、财力就变出其中任意一条路出来。

秦始皇希望徐福能把要修的n-1条路中最长的那条变出来，但是徐福希望能把要求的人力数量最多的那条变出来。对于每条路所需要的人力，是指这条路连接的两个城市的人数之和。

最终，秦始皇给出了一个公式，A/B，A是指要徐福用魔法变出的那条路所需人力， B是指除了徐福变出来的那条之外的所有n-2条路径长度之和，选使得A/B值最大的那条。

分析：

A/B 要最大 那么 B 就应该最小，为了使 B 最小，可以求最小生成树，去掉权值最大的边，对于找权值最大边，两重循环枚举即可，如果该边在最小生成树上，直接去掉，如果不在最小生成树上，必然会产生一个环，那么去掉这一个环上的最大边，这就是次小生成树的算法。

#include <iostream>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max =  + ;

int po[Max], X[Max], Y[Max];

int T, n;

double G[Max][Max], maxlen[Max][Max];

bool used[Max], eused[Max][Max];

double mincost[Max];

int mincostfrom[Max];

double prime()

{

    memset(used, , sizeof(used));

    memset(eused, , sizeof(eused));

    memset(maxlen, , sizeof(maxlen));

    double ans = ;

    mincostfrom[] = ;  // 一个边有两个顶点，这个mincost[i] = j，表示 j - i 这样一条边

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

        mincost[i] = INF;

    mincost[] = ;

    int added = ;

    while (added < n)

    {

        double cost = (double) INF;

        int from, to;

        for (int t = ; t < n; t++)

        {

            if (used[t] ==  && cost > mincost[t])

            {

                from = mincostfrom[t];

                to = t;

                cost = mincost[t];

            }

        }

        added++;

        ans += cost;

        eused[from][to] = eused[to][from] = ;  // 在最小生成树上

        used[to] = ;

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

        {

            if (used[i] && to != i)

                maxlen[i][to] = maxlen[to][i] = max(maxlen[i][from], max(maxlen[i][to], G[from][to]));  // maxlen[i][j] 表示 i 和 j之间权值最大边，找到一个边就要更新

        }

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

        {

            if (!used[i] && G[to][i] < mincost[i])

            {

                mincost[i] = G[to][i];

                mincostfrom[i] = to;

            }

        }

    }

    return ans;

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d", &n);

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

        {

            scanf("%d%d%d", &X[i], &Y[i], &po[i]);

        }

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

        {

            for (int j = i + ; j < n; j++)

            {

                double dis = sqrt((double) (X[j] - X[i]) * (X[j] - X[i]) + (double) (Y[j] - Y[i]) * (Y[j] - Y[i]));

                G[i][j] = G[j][i] = dis;

            }

        }

        double mst = prime();

        //cout << mst << endl;

        double ans = ;

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

        {

            for (int j = i + ; j < n; j++)

            {

                double popu = po[i] + po[j];

                double tollen;

                if (eused[i][j])

                {

                    tollen = mst - G[i][j];

                }

                else

                {

                    tollen = mst - maxlen[i][j];

                }

                ans = max(ans, popu / tollen);

            }

        }

       // cout << ans << endl;

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

    }

    return ;

}