为什么好几个测试的都read负号了呀,负号从哪里来的
查看原帖
为什么好几个测试的都read负号了呀,负号从哪里来的
630992
djsavu楼主2022/4/20 16:57
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<numeric>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<functional>
#include<bitset>
#include<math.h>
#include<cstring>
#include<iomanip>
#pragma warning(disable:4996)
#define ll long long
#define INF 0X3f3f3f3f
#define mod 80112002
using namespace std;
const int maxn = 1010;//最大点数
const int maxm = 1e6;//最大边数
int n = 0, m = 0;
int tot = 0;
struct Node {
	int x, y;
	long double distance(const Node& a) {
		return sqrt((a.x - x)*(a.x - x) + (a.y - y)*(a.y - y));
	}
}node[maxn];
struct Edge {
	int u, v;
	long double w;
	bool operator<(const Edge&x)const {
		return w < x.w;
	}
}edge[maxm];

long double dist[maxn][maxn];
int fa[maxn];

int find(int x) {
	while (x != fa[x])
		x = fa[x] = fa[fa[x]];
	return x;
}
void kruskal() {
	sort(edge + 1, edge + tot + 1);
	int eu = 0, ev = 0, cnt = 0;
	long double ans = 0.0;
	for (int i = 1; i <= tot; ++i) {
		eu = find(edge[i].u), ev = find(edge[i].v);
		if (eu == ev)
		{
			continue;
		}
		//若出现两个点已经联通了,则说明这一条边不需要了
		ans += edge[i].w;
		//将此边权计入答案
		fa[ev] = eu;
		//将eu、ev合并
		if (++cnt == n - 1)
		{
			break;
		}
		//循环结束条件,及边数为点数减一时,此时共合并了n-1次。
	}
	cout << fixed << setprecision(2) << ans;
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> node[i].x >> node[i].y;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			dist[i][j] = node[i].distance(node[j]);
		}
		dist[i][i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		dist[a][b] = dist[b][a] = 0;//把原有的边赋为0
	}
	for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			edge[++tot] = { i,j,dist[i][j] };//把所有点都连起来
		}
	}
	kruskal();
	return 0;
}
2022/4/20 16:57
加载中...