首页 > 代码库 > POJ 2560 Freckles Prime算法题解
POJ 2560 Freckles Prime算法题解
本题是求最小生成树。
给出的是坐标节点,然后需要根据这些坐标计算出各个点之间的距离。
除此就是标准的Prime算法了,能使用Prime的基本上都可以使用Kruskal。
这些经典的算法一定要多写,熟练掌握,否则很难灵活运用的。
而且经典的算法之所以为经典,原因之一是没那么容易自己凭空想象出来的,所以要熟练。
#include <stdio.h> #include <string.h> #include <queue> #include <float.h> #include <algorithm> #include <math.h> using namespace std; struct Point { float x, y; }; const int MAX_N = 101; Point P[MAX_N]; bool vis[MAX_N]; float dist[MAX_N]; float minDist[MAX_N]; float calDist(Point &a, Point &b) { float x = a.x - b.x; float y = a.y - b.y; return sqrtf(x*x + y*y); } void Prime(int n) { memset(vis, 0, sizeof(bool) * (n+1)); vis[1] = true; dist[1] = 0; for (int i = 2; i <= n; i++) { dist[i] = calDist(P[1], P[i]); } for (int i = 1; i < n; i++) { float minD = FLT_MAX; int id = 0; for (int j = 2; j <= n; j++) { if (!vis[j] && dist[j] < minD) { minD = dist[j]; id = j; } } vis[id] = true; minDist[i] = minD; for (int j = 2; j <= n; j++) { if (!vis[j]) { float d = calDist(P[id], P[j]); if (d < dist[j]) dist[j] = d; } } } } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%f %f", &P[i].x, &P[i].y); } Prime(n); float ans = 0.f; for (int j = 1; j < n; j++) { ans += minDist[j]; } printf("%.2f\n", ans); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。