hdu1162Eddy's picture 最小生成树

╮(╯_╰)╭模板是距离已知 这个多算个欧式距离

Problem Description
Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzzled,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your duty discover the shortest length which the ink draws?
 

Input
The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.

Input contains multiple test cases. Process to the end of file.
 

Output
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points.
 

Sample Input
3 1.0 1.0 2.0 2.0 2.0 4.0
 

Sample Output
3.41
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int flag1=0;
double sum;
double arr_list[110][110];
struct Edge
{
     int point;
     double lowcost;
     int flag;
};
Edge edge[12100];
struct Point
{
     double x,y;
}point[110];
double prim(int n)
{
     int i,j,k=1,flag;
     double min,sum2=0;
     j=1;
     for(i=1;i<=n;i++)
     {
          if(i!=j)
          {
               edge[i].point=i;
               edge[i].lowcost=arr_list[j][i];
               edge[i].flag=0;
          }
     }
     edge[j].lowcost=0;
     edge[j].flag=1;
     for(i=2;i<=n;i++)
     {
          k=1;
          min=65535;
          flag=0;
          for(j=2;j<=n;j++)
          {
               if(edge[j].flag==0&&edge[j].lowcost<min)
               {
                    k=j;
                    min=edge[j].lowcost;
                    flag=1;
               }
          }
          if(!flag) return -1;
          sum2+=min;
          edge[k].flag=1;
          for(j=2;j<=n;j++)
          {
               if(edge[j].flag==0&&arr_list[k][j]<edge[j].lowcost)
               {
                    edge[j].point=k;
                    edge[j].lowcost=arr_list[k][j];
               }
          }
     }
     return sum2;
}
int main()
{
   // freopen("cin.txt","r",stdin);
    int n;
    while(~scanf("%d",&n))
    {
         for(int i=1;i<=n;i++)
         {
              cin>>point[i].x>>point[i].y;
              arr_list[i][i]=65535;
         }
         for(int i=1;i<n;i++)
         {
              for(int j=i+1;j<=n;j++)
              {
                   arr_list[i][j]=sqrt(pow((point[i].x-point[j].x),2)+pow((point[i].y-point[j].y),2));
                   arr_list[j][i]=arr_list[i][j];
                   //cout<<arr_list[i][j]<<endl;
              }
         }
         sum=prim(n);
         printf("%.2lf\n",sum);
    }
    return 0;
}


全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 13:05
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务