這題好題啊，網(wǎng)上也有很多解題報(bào)告的呢，哥也是看了才懂寫的。。
直接貼代碼。這個代碼不咋地呢。
分?jǐn)?shù)規(guī)劃用迭代法500+ms，用二分法就2000+ms了。可見差異還是挺大的，還是迭代法好。
膜拜下分?jǐn)?shù)規(guī)劃算法的創(chuàng)始人
#include <stdio.h>
#include <math.h>
#include <string.h>
int X[1024], Y[1024], Z[1024], N, from[1024];
char mst[1024];
double D[1024], rate;
struct 
{
double w, cost, len;
} E[1024][1024];
double prim(double L)
{
int i, j;
double res, cost, len;
for (i = 0; i < N; i++)
for (j = i; j < N; j++)
E[i][j].w = E[j][i].w = E[i][j].cost - E[i][j].len * L;
for (i = 0; i < N; i++) {
D[i] = E[0][i].w;
from[i] = 0;
}
memset(mst, 0, N);
mst[0] = 1;
res = cost = len = 0;
for (i = 0; i < N - 1; i++) {
double min_d;
int min_i;
min_d = 1e50;
for (j = 0; j < N; j++) {
if (!mst[j] && D[j] < min_d) {
min_d = D[j];
min_i = j;
}
}
mst[min_i] = 1;
res += min_d;
cost += E[min_i][from[min_i]].cost;
len += E[min_i][from[min_i]].len;
for (j = 0; j < N; j++) {
if (!mst[j] && E[min_i][j].w < D[j]) {
D[j] = E[min_i][j].w;
from[j] = min_i;
}
}
}
rate = cost / len;
return res;
}
void solve()
{
/**//*
double l, r, m;
l = 0;
r = 1000;
while (r - l > 0.0001) {
m = (r + l) / 2;
if (prim(m) > 0)
l = m;
else
r = m;
}
*/
double r;
int i, j;
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
double dx, dy;
dx = (double)X[i] - X[j];
dy = (double)Y[i] - Y[j];
E[i][j].cost = E[j][i].cost = fabs((double)Z[i] - Z[j]);
E[i][j].len = E[j][i].len = sqrt(dx*dx + dy*dy);
}
}
rate = 0;
do {
r = rate;
prim(rate);
} while (fabs(r - rate) > 0.0001);
printf("%.3f\n", rate);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
while (1) {
scanf("%d", &N);
if (!N)
break;
for (i = 0; i < N; i++)
scanf("%d%d%d", &X[i], &Y[i], &Z[i]);
solve();
}
return 0;
}