kruskal 为什么只有20分(-"-怒)
查看原帖
kruskal 为什么只有20分(-"-怒)
873786
wangjiajinself楼主2023/12/24 17:19
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,father[1005],cnt=0,ans=0;
double hd[505],flag;
struct Point1{
	int x,y;
}a[1005];
struct PointDis{
	int x,y;
	double z;
}dis[1000005];
int find(int x)
{
	if(x==father[x]) return x;
	return father[x]=find(father[x]);
}
double Dis(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1*y2));
}
bool cmp(PointDis a,PointDis b)
{
	return a.z<b.z;
}
int main() {
	cin>>m;
	for(int i=1;i<=m;i++)
	cin>>hd[i];
	cin>>n;
	for(int i=1;i<=n;i++)
	father[i]=i;
	for(int i=1;i<=n;i++)
	cin>>a[i].x>>a[i].y;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		cnt++;
		dis[cnt].x=i;
		dis[cnt].y=j;
		dis[cnt].z=Dis(a[i].x,a[i].y,a[j].x,a[j].y);
	}
	sort(dis+1,dis+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		int px=find(dis[i].x);
		int py=find(dis[i].y);
		if(px==py) continue;
		father[px]=py;
		flag=dis[i].z;
	}
	for(int i=1;i<=m;i++)
	if(hd[i]*1.0>=flag) ans++;
	cout<<ans;
	return 0;
}
2023/12/24 17:19
加载中...