Kruskal 30分求助
查看原帖
Kruskal 30分求助
542199
dxt_楼主2024/3/16 15:46
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
	int u,v;
	double w;
}e[N];
int n,m,cnt,ans,num,ansn,a[N],x[N],y[N],fa[N];
double dis(int x,int y,int x2,int y2){
	double s=(double)sqrt((double)(x-x2)*(double)(x-x2)+(double)(y-y2)*(double)(y-y2));
	return s;
}
int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
bool cmp(node &a,node &b){
	return a.w<b.w;
}
void kruskal(){
  for(int i=1,x,y;i<=cnt&&num!=n-1;++i){
    x=find(e[i].u);y=find(e[i].v);
    if(x==y) continue;
    fa[x]=y;ans=e[i].w;++num;
  }
}
int main(){
	scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);for(int i=1;i<=m;++i) fa[i]=i;
	for(int i=1;i<=m;++i) scanf("%d%d",&x[i],&y[i]);
  	for(int i=1;i<=m;++i)
	for(int j=1;j<=m;++j)
	if(i!=j) e[++cnt].u=i,e[cnt].v=j,e[cnt].w=dis(x[i],y[i],x[j],y[j]);
  	sort(e+1,e+1+cnt,cmp);kruskal();
  	for(int i=1;i<=m;++i) if(ans<=a[i]) ansn++;
  	printf("%d",ansn);
	return 0;
}
2024/3/16 15:46
加载中...