求助,已AC,但不知道为什么
查看原帖
求助,已AC,但不知道为什么
422996
HeCao2008楼主2022/10/22 17:50
#include<bits/stdc++.h>
#define db double
using namespace std;
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 compare(edge a,edge b){
	return a.w<b.w;
}
int find(int x){
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
void kruskal(){
	int now=0;
	sort(a+1,a+cnt+1,compare);
	for(int i=1;i<=cnt;i++){
		now++;
		if(find(a[now].u)!=find(a[now].v)){
			ans+=a[now].w;
			fa[find(a[now].u)]=find(a[now].v);
		}
//		if(now>=n)break;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>aa[i].x>>aa[i].y;
	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++){
		a[++cnt].u=i;
		a[cnt].v=j;
		a[cnt].w=(db)sqrt((db)(aa[i].x-aa[j].x)*(aa[i].x-aa[j].x)+(db)(aa[i].y-aa[j].y)*(aa[i].y-aa[j].y));
	} 
	for(int i=1;i<=m;i++){
		int aaa,bbb;
		cin>>aaa>>bbb;
		a[++cnt].u=aaa;
		a[cnt].v=bbb;
		a[cnt].w=0.0;
	}
	
	kruskal();
	cout<<fixed<<setprecision(2)<<ans<<endl;
	return 0;
}

上面是AC代码,前几次我交只过了10分,唯一的区别在于我之前的加了这句话

if(now>=n)break; //AC程序中这句话是注释掉的

我记得最小生成树板子就得加上这句话(因为已经连了所有的边)但是为什么这道题不行呢

2022/10/22 17:50
加载中...