本文主要是介绍poj 2728 Desert King 最优比率生成树 分数规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始读题意可能有点难懂。
题意：
给你n个村庄的坐标点，它们都有一个海拔高度（你可以想象为三维空间）。现在让你给村庄通水，水道只能水平得建，即平行于地面。
每个水道的长度为村庄的水平距离（无视海拔高度），费用为两个村庄的海拔高度的差值。
现在只要修n-1条水道，让你求出 总费用/总长度 的最小比率。
思路：
分数规划
假设answer为最小的比率，answer <= sum(cost[i]*x[i])/sum(length[i]*x[i])，则有 sum(cost[i]*x[i]) - answer*sum(length[i]*x[i]) >= 0;
则我们就是要找出一个answer，使得对于所有的方案，都要有上面的不等式成立，并且其中至少有一个方案结果恰好等于0；
二分answer，每次把每条边的权值根据上面的式子求出来，跑最小生成树（因为是个完全图，要用prime算法）
二分范围0~100（实际上我也不知道为什么范围可以这么小。。。）
*后来我试了下Dinkelbach，二分要2000+ms，后者只需200+ms
code：
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;typedef long long LL;
const int MAXN = 1e3+5;
const double eps = 1e-9;
const double INF = 1e15;struct Village
{int x, y;int altitude;
}v[MAXN];int n;
bool vis[MAXN];
double a[MAXN][MAXN], b[MAXN][MAXN];
double w[MAXN][MAXN];
double d[MAXN];
int par[MAXN];int in()
{char ch;int val = 0;ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9') {val = val*10 + ch-'0'; ch = getchar();}return val;
}void input()
{for(int i = 1;i <= n; i++){v[i].x = in();v[i].y = in();v[i].altitude = in();}for(int i = 1;i <= n; i++)for(int j = i+1;j <= n; j++){a[i][j] = a[j][i] = abs(v[i].altitude-v[j].altitude);b[i][j] = b[j][i] = sqrt(1.0*(v[i].x-v[j].x)*(v[i].x-v[j].x) + 1.0*(v[i].y-v[j].y)*(v[i].y-v[j].y));}
}double Prime()
{memset(vis, false, sizeof(vis));for(int i = 1; i<=n; i++)d[i] = INF;double t1 = 0, t2 = 0;d[1] = 0;for(int i = 1;i <= n; i++){int u;double minv = INF;for(int j = 1;j <= n; j++){if(!vis[j] && d[j] < minv)u = j, minv = d[j];}if(u == -1) break;vis[u] = true;for(int j = 1;j <= n; j++){if(!vis[j] && w[u][j] < d[j]){d[j] = w[u][j];par[j] = u;}}if(u == 1) continue;t1 += a[par[u]][u];t2 += b[par[u]][u];}return t1/t2;
}double check(double mid)
{for(int i = 1;i <= n; i++)for(int j = i+1;j <= n; j++)w[j][i] = w[i][j] = a[i][j] - mid*b[i][j];return Prime();
}void solve()
{double a = 0, b;while(true){b = check(a);if(fabs(a-b) < eps) break;a = b;}printf("%.3f\n", b);
}int main()
{while(true){n = in();if(n == 0) break;input();solve();}return 0;
}
这篇关于poj 2728 Desert King 最优比率生成树 分数规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
