題目意思：
有n個村莊，村莊在不同坐標和海拔，現在要對所有村莊供水，只要兩個村莊之間有一條路即可，建造水管距離為坐標之間的歐幾裡德距離，費用為海拔之差，現在要求方案使得費用與距離的比值最小，很顯然，這個題目是要求一棵最優比率生成樹。
0-1規劃：
概念
有帶權圖G, 對於圖中每條邊e[i], 都有benifit[i](收入)和cost[i](花費), 我們要求的是一棵生成樹T, 它使得 ∑(benifit[i]) / ∑(cost[i]), i∈T 最大(或最小).這顯然是一個具有現實意義的問題.
解法之一 0-1分數規劃
設x[i]等於1或0, 表示邊e[i]是否屬於生成樹.
則我們所求的比率 r = ∑(benifit[i] * x[i]) / ∑(cost[i] * x[i]), 0≤i<m .
為了使 r 最大, 設計一個子問題---> 讓 z = ∑(benifit[i] * x[i]) - l * ∑(cost[i] * x[i]) = ∑(d[i] * x[i]) 最大 (d[i] = benifit[i] - l * cost[i]) , 並記為z(l). 我們可以興高采烈地把z(l)看做以d為邊權的最大生成樹的總權值.
然後明確兩個性質:
1. z單調遞減
證明: 因為cost為正數, 所以z隨l的減小而增大.
2. z( max(r) ) = 0
證明: 若z( max(r) ) < 0, ∑(benifit[i] * x[i]) - max(r) * ∑(cost[i] * x[i]) < 0, 可化為 max(r) < max(r). 矛盾;
若z( max(r) ) >= 0, 根據性質1, 當z = 0 時r最大.
代碼：
if變量後面可以切換使用二分和迭代。if 0是二分，if 1是迭代，迭代300ms+，二分1400ms+
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define nMax 1050
#define inf 0x7fffffff
static double eps = 1e-4;
int vis[nMax],x[nMax],y[nMax],z[nMax],pre[nMax];
double dis[nMax],cost[nMax][nMax],dist[nMax][nMax];
int n;
double prim(double x)//普利姆算法求最小生成樹
{
double totalcost = 0, totaldist = 0;
double sum = 0.0;
for (int i = 1; i <= n; ++ i)
{
pre[i] = 1;
}
dis[1] = 0;
memset(vis, 0, sizeof(vis));
vis[1] = 1;
for (int i = 2; i <= n; ++ i)
{
dis[i] = cost[1][i] - dist[1][i] * x;
}
int k;
for (int i = 2; i <= n; ++ i)
{
double minCost = inf;
for (int j = 2; j <= n; ++ j)
{
if (!vis[j] && dis[j] < minCost)
{
minCost = dis[j];
k = j;
}
}
vis[k] = 1;
sum += minCost;//for 二分
totalcost += cost[pre[k]][k];
totaldist += dist[pre[k]][k];
for (int j = 1; j <= n; ++ j)
{
if (!vis[j] && dis[j] > cost[k][j] - dist[k][j] * x)
{
dis[j] = cost[k][j] - dist[k][j] * x;
pre[j] = k;
}
}
}
#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;
}
