none
杭电 1162 http://acm.hdu.edu.cn/showproblem.php?pid=1162 RRS feed

  • 问题

  • 这个题目 我是这样想的了,先求出任意两点之间的的距离,然后,从一点(如 A点)开始寻找一个与他最近的点B,然后又从找到的点B开始,找与他最近的点,假如是C,然后判断AC之间的距离是否比BC之间的距离短,若短,则成为新的最短距离,这样依次寻找下去,直至所有的点都找完。下面是我的程序,不知道哪里错了,望各位同志们指教一二。

    #include "stdio.h"
    #include "math.h"

    double calculate(double x1,double y1,double x2,double y2)
    {
     double x,y;
     x = fabs(x1 - x2);
     y = fabs(y1 - y2);
     return sqrt(x * x + y * y);
    }
    int main()
    {
     int n,i,j,h,k,temp,mark,flag,state;
     double point[100][2],distance[100][100],shortest[100][2],min;
     while((scanf("%d",&n)) != EOF)
     {
      temp = n;
      for(i = 0; i < n; i ++)
      {
       scanf("%lf%lf",&point[i][0],&point[i][1]);
      }
      for(i = 0; i < n - 1; i ++)
      {
       distance[i][i] = 0;
       for(j = i + 1; j < n; j ++)
       {
        distance[i][j] = calculate(point[i][0],point[i][1],point[j][0],point[j][1]);
        distance[j][i] = distance[i][j];
       }
      }
      distance[i][i] = 0;
      k = 0;
      i = 0;
      while(-- temp)
      {
       min = 10000000;
       mark = -1;
       for(j = 0; j < n; j ++)
       {
        if(distance[i][j] == 0)
        {
         continue;
        }
        if(min > distance[i][j])
        {
         for(h = 0; h < k; h ++)
         {
          if(j == shortest[h][0])
          {
           break;
          }
         }
         if(h == k)
         {
          mark = j;
          min = distance[i][j];
         }
        }
       }
       state = 0;
       if(k != 0)
       {
        for(h = 0; h < k; h ++)
        {
         if(distance[(int)shortest[h][0]][mark] < min)
         {
          state = 1;
          min = distance[(int)shortest[h][0]][mark];
          flag = (int)shortest[h][0];
         }
        }
       }
       shortest[k][0] = (double)i;
       shortest[k][1] = min;
       if(state == 0)
       {
        distance[i][mark] = 0;
        distance[mark][i] = 0;
       }
       else
       {
        distance[mark][flag] = 0;
        distance[flag][mark] = 0;
       }
       i = mark;
       k ++;
      }
      min = 0;
      for(i = 0; i < k; i ++)
      {
       min += shortest[i][1];
      }
      printf("%0.2lf\n",min);
     }
     return 0;
    }


    一生只为自己珍视的人奋斗,哪怕是牺牲自己。
    2011年7月11日 1:58

答案

  • 你好:

     

    当需要计算的点只有2个,且这2个点的位置重合的时候,他们之间的距离应该为0.然而通过您的程序计算得出的结果却是10000000。这是由于您在处理边界值的时候没有进行判断所造成的。

     

    希望我的回答对您的问题有所帮助。

     


    Rob Pan [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    • 已标记为答案 Rob Pan 2011年7月25日 8:13
    2011年7月21日 9:53

全部回复

  • 你好,

     

    根据您的代码,由于您在设置最小距离的时候没有判断2个相同点之间的距离,因而造成了输出值为默认最小值。例如在输入两个左边分别为:1.0 0 1. 0 0 得到的结果为10000000. 所以您可以考虑在这里加一个判断。

     

    同时,您的这个问题应该是求最短路径算法,所以我建议您可以在参考Dijkstra算法或者Floyd算法。

     

    希望我的回答对您的问题有所帮助


    Rob Pan [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    2011年7月12日 7:52
  • 有点没动懂的意思,能否说得更详细点。这个题可以用prim或kruskal算法解决,我用这两种方法已经做出来,但我觉得上的方法可以尝试,但出错了。还请你指点指点。


    一生只为自己珍视的人奋斗,哪怕是牺牲自己。
    2011年7月15日 5:01
  • 你好:

     

    当需要计算的点只有2个,且这2个点的位置重合的时候,他们之间的距离应该为0.然而通过您的程序计算得出的结果却是10000000。这是由于您在处理边界值的时候没有进行判断所造成的。

     

    希望我的回答对您的问题有所帮助。

     


    Rob Pan [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    • 已标记为答案 Rob Pan 2011年7月25日 8:13
    2011年7月21日 9:53