自动搬运

查看原文

来自洛谷，原作者为

	哥就是拽 樱花花瓣掉落的速度是5cm/秒，我又要以怎样的速度生活，才能再次遇见你

搬运于2025-08-24 21:38:25，当前版本为作者最后更新于2019-03-07 20:37:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目很水
代码简单易懂
偷看了一下标签

没错就是生成树！！！

思路：

把两个点之间的距离算出来，一边Kruskal，记录下最大的边，和每只猴子的跳跃距离比较一下，如果跳跃距离大就ans++。

最后附上代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans=0;
double sum=-1;
int a[1000005][3],b[1000005],pre[1000005];//	前面一直RE，开大一点；

struct zzz {
	int x,y;
	double p;
} z[1000005];

int cmp(zzz k,zzz d) {
	return k.p<d.p;
}

int find(int x) {
	if(pre[x]==x)
		return x;
	return pre[x]=find(pre[x]);
}

int main() {
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>b[i];
	}
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i][1]>>a[i][2];
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i!=j) {
				k++;
				z[k].x=i;
				z[k].y=j;
				z[k].p=sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][2]));
			}
		}
	}	
	int cnt=n;//Kruskal！！！
	sort(z+1,z+k+1,cmp);
	for(int i=1; i<=n; i++) {
		pre[i]=i;
	}
	for(int i=1; i<=k; i++) {
		if(cnt==1)
			break;
		int s1=find(z[i].x),s2=find(z[i].y);
		if(s1!=s2) {
			pre[s1]=s2;
			cnt--;
			sum=z[i].p;
		}
	}
	for(int i=1; i<=m; i++) {//比较
		if(sum<=b[i])
			ans++;
	}
	cout<<ans<<endl;//完美输出
	return 0;
}

第三次发题解，有错误请各位神犇指点

最后安利一下我的博客