转载：http://blog.csdn.net/sdj222555/article/details/7490797网上有一些很数学的证明方法，表示看的挺晕，自己理解了一下后，发表下自己的看法，如果有错误，再进行修改其实原题就是求 MIN（ ∑CiXi / ∑DiXi ） Xi∈{0，1} ，对每个生成树，设其比率r=∑CiXi / ∑DiXi ，可得∑CiXi - ∑DiXi * r=0（条件1）那么对于所有的生成树，显然∑CiXi - ∑DiXi * min(r) >= 0，当 ∑CiXi / ∑DiXi = min(r)时，等号成立。 而我们现在不知道min(r)是多少，只好进行枚举，对每个枚举的r ,构建新的权值（Ci-Di*r），然后求最小生成树， 为什么求最小呢？ 我的理解就是这是为了寻找使得生成树的总权值为0的可能性，因为只有当其等于0 的时候，才满足了条件1 这个条件， 说明这个r是可行的，并且如果r枚举到值为min(r)时，其最小生成树的的总权值必然恰好等于0，但是如果不能等于0， 比如大于0， 显然是对该r值，所有的生成树上无论如何也满足不了条件1，说明r值就是偏小了。同理如果小于0，r值是偏大的,说明可能存在某些生成树使得满足条件1，而我们的目标是在满足条件1的情况下使得r最小。根据这个我们可以发现，实际上r的值是可以进行二分查找的。 而也有人给出了更为高效的迭代方法。 poj 2728二分法#include #include #include #include #include #include #include #define MAXN 1005#define INF 1000000000#define eps 1e-7using namespace std;int n;double Edge[MAXN][MAXN], lowcost[MAXN];int nearvex[MAXN];struct Point{ int x, y, z;}p[MAXN];double cal(int a, int b){ return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y));}double prim(int src, double l){ double cost = 0, len = 0; double sum = 0; for(int i = 1; i <= n; i++) { nearvex[i] = src; lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l; } nearvex[src] = -1; for(int i = 1; i < n; i++) { double mi = INF; int v = -1; for(int j = 1; j <= n; j++) if(nearvex[j] != -1 && lowcost[j] < mi) { v = j; mi = lowcost[j]; } if(v != -1) { cost += abs(p[nearvex[v]].z - p[v].z); len += Edge[nearvex[v]][v]; nearvex[v] = -1; sum += lowcost[v]; for(int j = 1; j <= n; j++) { double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l; if(nearvex[j] != -1 && tmp < lowcost[j]) { lowcost[j] = tmp; nearvex[j] = v; } } } } return sum;}int main(){ while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) Edge[i][j] = cal(i, j); double low = 0, high = 10.0; //其实二分20多次已经很足够了 double l = 0.0, r = 100.0, mid; while(r - l > eps) { mid = (l + r) / 2; if(prim(1, mid) >= 0) l = mid; else r = mid; } printf("%.3f\n", r); } return 0;}
迭代法：#include #include #include #include #include #include #include #define MAXN 1005#define INF 1000000000#define eps 1e-7using namespace std;int n;double Edge[MAXN][MAXN], lowcost[MAXN];int nearvex[MAXN];struct Point{ int x, y, z;}p[MAXN];double cal(int a, int b){ return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y));}double prim(int src, double l){ double cost = 0, len = 0; for(int i = 1; i <= n; i++) { nearvex[i] = src; lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l; } nearvex[src] = -1; for(int i = 1; i < n; i++) { double mi = INF; int v = -1; for(int j = 1; j <= n; j++) if(nearvex[j] != -1 && lowcost[j] < mi) { v = j; mi = lowcost[j]; } if(v != -1) { cost += abs(p[nearvex[v]].z - p[v].z); len += Edge[nearvex[v]][v]; nearvex[v] = -1; for(int j = 1; j <= n; j++) { double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l; if(nearvex[j] != -1 && tmp < lowcost[j]) { lowcost[j] = tmp; nearvex[j] = v; } } } } return cost / len;}int main(){ while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) Edge[i][j] = cal(i, j); double a = 0, b; while(1) { b = prim(1, a); if(fabs(a - b) < eps) break; a = b; } printf("%.3f\n", b); } return 0;}