20分,求助
查看原帖
20分,求助
549027
__JiCanDuck__楼主2023/2/13 16:32
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

const int kMaxN = 1005;

int n, m, cnt, fa[kMaxN * kMaxN];
double x[kMaxN], y[kMaxN];
double ans;

struct note {
  int x, y;
  double w;
  friend bool operator<(const note &A, const note &B) {
    if (A.w == B.w) {
      return A.x < B.x;
    } else {
      return A.w < B.w;
    }
  }
} a[kMaxN * kMaxN];

double gougu(double x, double y) {
  return sqrt(x * x + y * y);
}

int find(int x) {
  return (fa[x] == x ? x : find(fa[x]));
}

bool check(int x, int y) {
  return (find(x) == find(y));
}

void mix(int x, int y) {
  fa[x] = y;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      a[++cnt].x = i, a[cnt].y = j;
      a[cnt].w = gougu(x[i] - x[j], y[j] - y[i]);
    }
  }
	for (int i = 1; i <= cnt; i++) {
		fa[i] = i;
	}
  for (int j = 1, x, y; j <= m; j++) {
    cin >> x >> y;
    mix(x, y);
  }
  sort(a + 1, a + cnt + 1);
  int tot = 1;
  for (int i = 1; i <= cnt && tot <= n - 1 - m; i++) {
    if (!check(a[i].x, a[i].y)) {
      mix(a[i].x, a[i].y);
      tot++;
      ans += a[i].w;
    }
  }
  cout << fixed << setprecision(2) << ans;
  return 0;
}
2023/2/13 16:32
加载中...