Description：

每条边有两个值 $a_i$ 和 $b_i$ ，最小化 $\sum a_i/\sum b_i$ 使得图联通。

$1\le m \le 1000000$

Solution：

$01$ 分数规划，设二分答案为 $x$ ，要判断的就是 $\sum(a_i-xb_i)$ 与 $0$ 的关系，于是以 $a_i-xb_i$ 为边权做最小生成树即可。由于是完全图 $kruskal$ 瓶颈在 $n^2\log n$ 排序，所以要用 $prim$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 1010

int n;

int x[MAXN],y[MAXN],h[MAXN];

long double d1[MAXN][MAXN],d2[MAXN][MAXN];

long double d[MAXN][MAXN];

long double mind[MAXN];

bool ins[MAXN];

bool check(double x)

{

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

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

			d[i][j] = d1[i][j] - x * d2[i][j];

	long double res = 0;

	for(int i = 0;i <= n;++i)mind[i] = 1000000000;

	memset(ins,false,sizeof(ins));

	mind[1] = 0;

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

	{

		int k = 0;

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

			if(!ins[j] && mind[j] < mind[k])

				k = j;

		ins[k] = true;

		res += mind[k];

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

		{

			if(ins[j])continue;

			mind[j] = min(mind[j],d[k][j]);

		}

	}

	return res <= 0;

}

int main()

{

	while(scanf("%d",&n) && n != 0)

	{

		for(int i = 1;i <= n;++i)scanf("%d%d%d",&x[i],&y[i],&h[i]);

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

		{

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

			{

				d1[i][j] = abs(h[i] - h[j]);

				d2[i][j] = sqrt((long double)(x[i] - x[j]) * (long double)(x[i] - x[j]) + (long double)(y[i] - y[j]) * (long double)(y[i] - y[j]));

			}

		}

		long double l = 0,r = 1000000000,mid;

		while(r - l > 1e-6)

		{

			mid = (l + r) / 2;

			if(check(mid))r = mid;

			else l = mid;

		}

		printf("%.3Lf\n",l);

	}

	return 0;

}