Kruskal30pts求助ACon #2#3#4
查看原帖
Kruskal30pts求助ACon #2#3#4
1183074
xzy_AK_IOI楼主2024/8/7 09:41
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int N=1e3+10;
const int M=1e7+10;
int n,m;
int sum=0;
int monkey[N];
int tree_x[N];
int tree_y[N];
int dis(int x,int y,int x2,int y2){
	return (x-x2)*(x-x2)+(y-y2)*(y-y2);
}
struct edge{
	int from;
	int to;
	int w;
};
edge e[M];
bool pai(edge a,edge b){
	return a.w<b.w;
}
int s[N];
int find_set(int x){
	if (x!=s[x]){
		s[x]=find_set(s[x]);
	}
	return s[x];
}
void Kruskal(){
	sort(e+1,e+1+sum,pai);
	for (int i=1;i<=n;i++) s[i]=i;
	int ans=0,cnt=0;
	for (int i=1;i<=sum;i++){
		if (cnt==n-1) break;
		int e1=find_set(e[i].from);
		int e2=find_set(e[i].to);
		if (e1==e2) continue;
		s[e1]=e2;
		cnt++;
		ans=max(ans,e[i].w);
	}
	int a=0;
	for (int i=1;i<=n;i++){
		if (monkey[i]>=ans) a++;
	}
	cout<<a;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>monkey[i];
		monkey[i]*=monkey[i];
	}
	cin>>m;
	for (int i=1;i<=m;i++){
		cin>>tree_x[i]>>tree_y[i];
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=m;j++){
			if (i==j) continue;
			sum++;
			e[sum].from=i;
			e[sum].to=j;
			e[sum].w=dis(tree_x[i],tree_y[i],tree_x[j],tree_y[j]);
			sum++;
			e[sum].from=j;
			e[sum].to=i;
			e[sum].w=dis(tree_x[j],tree_y[j],tree_x[i],tree_y[i]);
		}
	}
	Kruskal();
	return 0;
}

2024/8/7 09:41
加载中...