数组长度要开大!!! 原代码(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....