Hud 1162 Eddy's picture[MST(kruscal)]

本文主要是介绍Hud 1162 Eddy's picture[MST(kruscal)]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

还是很基础的最小生成树

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=105;
const int Max=5005;
int n,top,father[N];
struct Point
{double x,y;
}point[N];
struct Line
{double a,b;double lenth;
}line[Max];
bool cmp(Line A,Line B)
{if(A.lenth<B.lenth) return true;return false;
}
void Init()
{for(int i=0;i<=n;i++)father[i]=i;top=0;
}
void input()
{for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);for(int i=1;i<=n;i++)//直接枚举所有的连线进行排序.{for(int j=i+1;j<=n;j++){line[top].a=i;line[top].b=j;line[top].lenth=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));top++;}}
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void kruscal()
{double min=0;sort(line,line+top,cmp);for(int  i=0;i<top;i++){int x=find(line[i].a);int y=find(line[i].b);if(x!=y){father[x]=y;min+=line[i].lenth;}}printf("%.2lf\n",min);
}
int main()
{while(~scanf("%d",&n)){Init();input();kruscal();}
}

1A

这篇关于Hud 1162 Eddy's picture[MST(kruscal)]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---