POJ 2728 二分+最小生成树

题意：给n个点，可以将每个点的x，y的欧几里得距离(就是坐标系里两点距离公式)看作距离，z的差值即为费用差，求的是所有最小生成树中的min（边费用和/边距离和）。

思路：其实挑战P143有类似的列题，用的是二分枚举答案的方法，只不过不是树。这一题仅仅需要将题给图找出最小生成树，然后同样枚举即可。

虽然网上有许多高级的名词什么最优比率xxx之类的。。以及迭代的方法，不过我认为用二分也很好，易于想到也可以加深理解。

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <cmath>

 #define MAXN 1005

 #define INF 1000000000

 #define eps 1e-7

 using 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 = , len = ;

     double sum = ;

     for(int i = ; i <= n; i++)

     {

         nearvex[i] = src;

         lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l;

     }

     nearvex[src] = -;

     for(int i = ; i < n; i++)

     {

         double mi = INF;

         int v = -;

         for(int j = ; j <= n; j++)

             if(nearvex[j] != - && lowcost[j] < mi)

             {

                 v = j;

                 mi = lowcost[j];

             }

         if(v != -)

         {

             cost += abs(p[nearvex[v]].z - p[v].z);

             len += Edge[nearvex[v]][v];

             nearvex[v] = -;

             sum += lowcost[v];

             for(int j = ; j <= n; j++)

             {

                 double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l;

                 if(nearvex[j] != - && tmp < lowcost[j])

                 {

                     lowcost[j] = tmp;

                     nearvex[j] = v;

                 }

             }

         }

     }

     return sum;

 }

 int main()

 {

     while(scanf("%d", &n) != EOF && n)

     {

         for(int i = ; i <= n; i++)

             scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);

         for(int i = ; i <= n; i++)

             for(int j = ; j <= n; j++)

                 Edge[i][j] = cal(i, j);

         double low = , high = 10.0;             //其实二分20多次已经很足够了

         double l = 0.0, r = 100.0, mid;

         while(r - l > eps)

         {

             mid = (l + r) / ;

             if(prim(, mid) >= ) l = mid;

             else r = mid;

         }

         printf("%.3f\n", r);

     }

     return ;

 }

巴特西

POJ 2728 二分+最小生成树

最新文章

热门文章