警示后人
查看原帖
警示后人
1376362
Lionel_Messi_10楼主2024/8/25 11:46

数组长度要开大!!! 原代码(20pts):

//Kruskal算法 :把所有边按边权排序 ,从小到大观察每一条边,边的两点不在一个块内,则选定该边并合并。 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2005;
double maxn;
int n,m,w[N],x[N],y[N],ans=0,tot=0,fa[N],item=0;
bool vis[N];
struct node{
	int u,v;
	double d;
}e[N];
double dist(int xx,int xx1,int yy,int yy1){
	return sqrt((xx-xx1)*(xx-xx1)+(yy-yy1)*(yy-yy1));
}
int findfa(int kkksc03){
	if(fa[kkksc03]==kkksc03) return kkksc03;
	else return fa[kkksc03]=findfa(fa[kkksc03]);
}
bool cmp(node A,node B){
	return A.d<B.d;
}
void Kruscal(){
	cin>>m;
	for(int i=1;i<=m;i++) cin>>w[i];
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			e[++tot].u=i,e[tot].v=j;
			e[tot].d=dist(x[i],x[j],y[i],y[j]);
		}
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		int fx=findfa(e[i].u),fy=findfa(e[i].v);
		if(fx==fy) continue;
		maxn=max(maxn,e[i].d);
		fa[fx]=fy;
		item++;
		if(item==n-1) break;
	}
	for(int i=1;i<=m;i++){
		if(w[i]>=maxn) ans++;
	}
	cout<<ans<<'\n';
	return ;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	Kruscal();
	return 0;
}

数组开大后:100pts....

2024/8/25 11:46
加载中...