Desert King(POJ2728+最优比率生成树+二分）

题目链接：http://poj.org/problem?id=2728

题目：

题意：求一颗生成树，使得费用与距离的比值最小，其中距离等于两点之间的平面欧拉距离，费用为z坐标之差。

思路：

　　由上图我们可以得知，我们只需对x进行二分（最大化平均值），以cost[i]-len[i]*x为边权跑prime即可。

代码实现如下：

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll, ll> pll;

 typedef pair<ll, int> pli;

 typedef pair<int, ll> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long ull;

 #define lson i<<1

 #define rson i<<1|1

 #define bug printf("*********\n");

 #define FIN freopen("D://code//in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = ;

 const int maxn =  + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f;

 int n, x, y, z;

 double ans;

 int vis[maxn];

 double mp[maxn][maxn], dis[maxn];

 struct node {

     int x, y ,z;

 }p[maxn];

 double dist(node& a, node& b) {

     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

 }

 bool prime(double x) {

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

         dis[i] = inf;

         vis[i] = ;

     }

     ans = ;

     dis[] = ;

     for(int i = ; ; i++) {

         double mx = inf;

         int t = -;

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

             if(!vis[j] & mx > dis[j]) {

                 mx = dis[j];

                 t = j;

             }

         }

         if(t == -) break;

         ans += mx;

         vis[t] = ;

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

             if(!vis[j] && dis[j] > fabs(p[t].z - p[j].z) - mp[t][j] * x) {

                 dis[j] = fabs(p[t].z - p[j].z) - mp[t][j] * x;

             }

         }

     }

     return ans >= ;

 }

 int main() {

     //FIN;

     while(~scanf("%d", &n) && n) {

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

             scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);

         }

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

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

                 mp[i][j] = dist(p[i], p[j]);

             }

         }

         double ub = , lb = , mid;

         while(ub - lb > eps) {

             mid = (ub + lb) / ;

             if(prime(mid)) lb = mid;

             else ub = mid;

         }

         printf("%.3f\n", lb);

     }

     return ;

 }