蒟蒻只过了样例,玄关,大佬快看我
查看原帖
蒟蒻只过了样例,玄关,大佬快看我
1285611
JiangMzz楼主2024/8/29 10:28
#include <bits/stdc++.h>
using namespace std;
int n, m, x[1001], y[1001], u[1001], v[1001];
double a[1001][1001];
int f[1001];
double j_dis(int x1, int y1, int x2, int y2) {
	return sqrt(pow(double(x1 - x2), 2) + pow(double(y1 - y2), 2));
}
struct data{
	int u, v;
	double w;
}e[1001];
bool cmp(data a, data b) {
	return a.w < b.w;
}
int findd(int x) {
	if (f[x] == x) return x;
	else return f[x] = findd(f[x]);
}
void join(int x, int y) {
	if (findd(x) != findd(y))
		f[findd(x)] = findd(y);
	return;
}
int cnt = 0;
double kruskal() {
	int num = n;
	double ans;
	for (int i = 1; i <= n; i++) 
		f[i] = i;
	sort(e + 1, e + 1 + cnt, cmp);
	for (int i = 1; i <= cnt; i++) {
		int u = e[i].u;
		int v = e[i].v;
		double w = e[i].w;
		if (findd(u) != findd(v)) {
			join(u, v);
			ans += w;
		//	cout << w << " " << i << endl;
			num--;
		}
		if (num == 1) break;
	}
	if (num != 1) return -1;
	return ans;
}
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 = i + 1; j <= n; j++) {
			a[i][j] = a[j][i] = j_dis(x[i], y[i], x[j], y[j]);
		}
	} 
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i];
		a[u[i]][v[i]] = a[v[i]][u[i]] = 0;		
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) {
				e[++cnt].u = i;
				e[cnt].v = j;
				e[cnt].w = a[i][j];	
			}	
		}
	}
	double ans = kruskal();
	printf("%.2lf", ans);
	return 0;
}
2024/8/29 10:28
加载中...