poj2728-最小比率生成树(二)

2013-01-25 17:51:19 · 作者: · 浏览: 804


  #if 0//0 for 二分, 1 for 迭代
  return totalcost / totaldist;
  #else
  return sum;
  #endif
  }
  int main()
  {
  while (scanf("%d", &n), n)
  {
  for (int i = 1; i <= n; ++ i)
  {
  scanf("%d%d%d", &x[i], &y[i], &z[i]);
  for (int j = 1; j < i; ++ j)
  {
  double tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
  cost[i][j] = cost[j][i] = abs(z[i] - z[j]);//海拔
  dist[i][j] = dist[j][i] = sqrt(tmp);//欧式距离
  }
  }
  double a = 0;
  #if 0//1为迭代,0为二分
  while (1)//迭代求最大值
  {
  double b = prim(a);

  if (abs(a - b) < eps)
  {
  printf("%.3f\n", a);
  break;
  }
  else
  a = b;
  }
  #else
  double head = 0,tail = 100000.0;
  while (tail - head > 1e-5)
  {
  double mid = (head + tail) / 2.0;
  a = prim(mid);
  if (a >= 0)
  {
  head = mid;
  }
  else
  tail = mid;
  }
  printf("%.3f\n", tail);
  #endif
  }
  return 0;
  }