题意要求a/b的最大值。 其中a是任意两点的点权和，b是除去这两点剩下的最小生成树的值。

我们可以先求出最小生成树，然后不断删边，然后求出删去这条边后的剩下的点的最小生成树的值（联想到次小生成树）。

删边的过程可以用dfs枚举。

代码如下啊：

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N = 1005;
int INF = 99999999;

int connect[N][N],  data[N][3], Dres[5];
int n, m;
double map[N][N], maxx[N][N] ,res = -INF, tempb;

void init()
{
    fill(connect[0], connect[0] + N * N, 0);
    fill(maxx[0], maxx[0] + N * N, 0);
    fill(map[0], map[0] + N * N, 0);
    res = -INF;
};

double getDis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
double prim()
{
    int mark[N], father[N];
    double dis[N], sum = 0;

    fill(mark, mark + N, 0);

    for (int i = 1; i <= n; i++)
    {
        dis[i] = map[1][i];
        father[i] = 1;
    }
    dis[1] = 0, mark[1] = 1 ;

    for (int i = 2; i <= n; i++)
    {
        double min1 = INF;
        
        int u = -1;

        for (int j = 1; j <= n; j++)if(mark[j] == 0 && min1 > dis[j])
        {
            u = j;
            min1 = dis[j];
        }
        sum += min1;
        mark[u] = 1;
        connect[u][father[u]] = connect[father[u]][u] = 2;
        maxx[u][father[u]] = maxx[father[u]][u] = min1;

        for (int j = 1; j <= n; j++)
        {
            if(j != u && mark[j] == 1)
            {
                maxx[j][u] = maxx[u][j] = max(maxx[j][father[u]], dis[u]);
            }
            if(mark[j] == 0 && dis[j] > map[u][j])
            {
                dis[j] = map[u][j];
                father[j] = u;
            }
        }
    }

    return sum;
};

void dfs(int index, int len, double a)
{
    if(index  == 3)
    {
        double b = tempb - maxx[Dres[1]][Dres[2]];
        double ab = a / b;
    //    printf("%d %d\n", Dres[1], Dres[2]);
        if(res < ab)
        {
            res = ab;
        }
        return;
    }
    else
    {
        for (int i = len; i <= n; i++)
        {
            Dres[index] = i ;
            dfs(index + 1, i + 1,a + data[i][2]);
        }
        return;
    }
    

};


/*
2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40
Sample Output
65.00
70.00
*/
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d %d", &data[i][0], &data[i][1], &data[i][2]);
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                connect[i][j] = connect[j][i] = 1;
                map[i][j] = map[j][i] = getDis(data[i][0], data[i][1], data[j][0], data[j][1]);
            }
        }

 
        tempb = prim();
        dfs(1, 1, 0);
        printf("%0.2lf\n", res);

     }
    



    return  0;
}