60pts求助,悬n关
查看原帖
60pts求助,悬n关
1027430
hlb44楼主2025/7/22 11:44

WA 2.8.9.10,望改正

#include<bits/stdc++.h>
using namespace std;
#define fo(i,begin,end) for(int i=begin;i<=end;i++)
#define db double
const int maxn=1014514;
const int maxx=1145;
int cnt=0;  // 计边
db ans=0.0; // 权值
struct Edge {
	db u,v,w;
} a[maxn];
struct Node {
	int x,y;   // 坐标
} aa[maxx];
db fa[maxx];
int n,m;
bool cmp(Edge a,Edge b) {
	return a.w<b.w;
}
int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void kruskal() {
	sort(a+1,a+cnt+1,cmp);
	int k=0;
	fo(i,1,cnt) {
		int u=a[i].u, v=a[i].v;
		if(find(u)!=find(v)) { 
			ans+=a[i].w;  // 累加边权到答案
			fa[find(u)]=find(v);  // 合并
			k++;  // 已选边数加1
			if(k==n-1) break;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	fo(i,1,n) cin>>aa[i].x>>aa[i].y;
	fo(i,1,n) fa[i]=i;
	fo(i,1,n) fo(j=i+1,j<=n,j++) {
		a[++cnt].u=i;
		a[cnt].v=j;
		a[cnt].w=sqrt((aa[i].x-aa[j].x)*(aa[i].x-aa[j].x)+(aa[i].y-aa[j].y)*(aa[i].y-aa[j].y));
	}
	// 处理已有边
	fo(i,1,m) {
		int u,v;
		cin>>u>>v;
		a[++cnt].u=u;
		a[cnt].v=v;
		a[cnt].w=0.0;
	}
	kruskal();
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}
2025/7/22 11:44
加载中...