POJ 2728 最优比率生成树

题意：
     让你求一颗最小比率生成树。
思路：
     我总结过了，在这里：http://blog.csdn.net/u013761036/article/details/26666261

     提示几个地方，这个题目的最小树记得用普利姆,别用克鲁斯卡尔，克鲁斯卡尔会超时，在sort那个地方超时。别的没啥。

#include<stdio.h> #include<math.h>#define INF 1000000000 #define eps 0.0001typedef struct {double x ,y ,z; }NODE;NODE node[1100]; int mark[1100]; double d[1100];double diss(NODE a ,NODE b) {double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);return sqrt(tmp); }double abss(double x) {return x > 0 ? x : -x; }double Prim(int n ,double L) {double ans = 0;for(int i = 2 ;i <= n ;i ++){double dis = diss(node[1] ,node[i]);//d[i] = dis - L * abss(node[1].z - node[i].z);d[i] = abss(node[1].z - node[i].z) - L * dis;mark[i] = 0;}mark[1] = 1;for(int ii = 1 ;ii < n ;ii ++){double Min = INF;int mk = -1;for(int i = 1 ;i <= n ;i ++){if(!mark[i] && d[i] < Min){mk = i;Min = d[i];}}if(mk == -1) return ans; ans += Min;mark[mk] = 1;for(int i = 1 ;i <= n ;i ++){if(mark[i]) continue;double dis = diss(node[mk] ,node[i]);//double tmp = dis - L * abss(node[mk].z - node[i].z);double tmp = abss(node[mk].z - node[i].z) - dis * L;if(d[i] > tmp) d[i] = tmp;}}return ans; }int main () {int n ,m ,i ,j;while(~scanf("%d" ,&n) && n){for(i = 1 ;i <= n ;i ++)scanf("%lf %lf %lf" ,&node[i].x ,&node[i].y ,&node[i].z);double low ,up ,mid ,ans = 0;low = 0 ,up = INF;while(up - low >= eps){mid = (low + up) / 2;double tmp = Prim(n ,mid);if(tmp >= 0)ans = low = mid;else up = mid;}printf("%.3f\n" ,ans);}return 0; }

总结

以上是生活随笔为你收集整理的POJ 2728 最优比率生成树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。