本文共 1067 字，大约阅读时间需要 3 分钟。
计算所有点之间的权值 然后就是最小生成树
#include #include #include #include #include #include #include using namespace std;struct point{ double x,y;};struct edge{ int u,v; double w; void f(int i, int j, double k) { u = i; v = j; w = k; } bool operator < (const edge &a) const { return w < a.w; }};edge e[10001];point p[101];int f[101];int n, l;int find2(int x){ return f[x] == x ? x : f[x] = find2(f[x]);}double solve(){ for(int i = 0; i < n; i++) f[i] = i; double s = 0; for(int i = 0; i < l; i++) { int a = find2(e[i].u), b = find2(e[i].v); if(a != b) { f[a] = b; s += e[i].w; } } return s;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } l = 0; for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) { e[l++].f(i, j, sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))); } sort(e,e+l); printf("%.2lf\n",solve()); if(t) puts(""); }}
转载于:https://www.cnblogs.com/avema/p/3774327.html