把两棵树之间能否跳过去看成边，所有树都能互达所需的最小跳距，等于一棵最小生成树中的最大边长；用 Prim 求出这个临界值后统计能达到的猴子数量。
OJ: luogu
题目 ID: P2504
难度:普及+/提高
标签:图论最小生成树贪心
日期: 2026-06-20 00:48
题意
给出若干只猴子的最大跳跃距离，以及 N 棵树的坐标。
如果一只猴子能在所有露出水面的树冠之间来回穿梭，也就是从任意一棵树出发，都能通过若干次跳跃到达其它所有树，那么这只猴子就算“可以在所有树冠上觅食”。
问一共有多少只猴子满足条件。
思路
先看一个直接按定义判断的小数据暴力：
cpp
// brute.cpp：枚举所有可能的跳跃阈值，直接检查图是否连通。
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 505;
const int MAXN = 1005;
int monkey_cnt, tree_cnt;
long long jump_len[MAXM];
long long x[MAXN], y[MAXN];
bool vis[MAXN];
long long dis2(int i, int j) {
long long dx = x[i] - x[j];
long long dy = y[i] - y[j];
return dx * dx + dy * dy;
}
bool connected(long long limit2) {
queue<int> q;
for (int i = 1; i <= tree_cnt; i++) {
vis[i] = false;
}
q.push(1);
vis[1] = true;
int cnt = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1; v <= tree_cnt; v++) {
if (vis[v]) {
continue;
}
if (dis2(u, v) > limit2) {
continue;
}
vis[v] = true;
q.push(v);
cnt++;
}
}
return cnt == tree_cnt;
}
long long brute_need() {
vector<long long> cand;
cand.push_back(0);
for (int i = 1; i <= tree_cnt; i++) {
for (int j = i + 1; j <= tree_cnt; j++) {
cand.push_back(dis2(i, j));
}
}
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
for (int i = 0; i < (int)cand.size(); i++) {
if (connected(cand[i])) {
return cand[i];
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> monkey_cnt;
for (int i = 1; i <= monkey_cnt; i++) {
cin >> jump_len[i];
}
cin >> tree_cnt;
for (int i = 1; i <= tree_cnt; i++) {
cin >> x[i] >> y[i];
}
long long need = brute_need();
int answer = 0;
for (int i = 1; i <= monkey_cnt; i++) {
if (jump_len[i] * jump_len[i] >= need) {
answer++;
}
}
cout << answer << '\n';
return 0;
}暴力做法是：
- 枚举一个跳跃上限
D - 把距离不超过
D的两棵树连边 - 检查整张图是否连通
- 找到让图第一次连通的最小
D
这个做法很好理解，但如果直接枚举所有可能距离并反复建图检查，效率一般。
关键观察是：题目真正要问的，不是哪只猴子能跳哪条边，而是：
想让所有树互相可达，单次跳跃距离至少要多大？
把每棵树看成点，两棵树之间的欧几里得距离看成边权。
如果某个跳跃上限 D 足够，那么只保留边权不超过 D 的边，图就应该连通。
而这个“最小可行的 D”，正好等于一棵最小生成树里的最大边长。
原因是：
- 最小生成树把所有点连起来
- 在所有生成树里，它会尽量让大边也压低
- 所以它的最大边，正是连通全图所需的最小临界值
这题点数只有 1000，直接用 Prim O(n^2) 很合适：
- 逐步把点加入生成树
- 每次记录新加入那条边的长度
- 这些边里最大的那一个，就是所需最小跳距
最后再统计有多少只猴子的最大跳跃距离不小于这个值即可。
实现时为了避免开根号，代码里全程比较距离平方：
- 边长用平方保存
- 猴子的跳跃能力也改成平方比较
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 505;
const int MAXN = 1005;
const long long INF = (1LL << 62);
int monkey_cnt, tree_cnt;
long long jump_len[MAXM];
long long x[MAXN], y[MAXN];
long long dist_to_tree[MAXN];
bool vis[MAXN];
long long dis2(int i, int j) {
long long dx = x[i] - x[j];
long long dy = y[i] - y[j];
return dx * dx + dy * dy;
}
long long prim_need() {
for (int i = 1; i <= tree_cnt; i++) {
dist_to_tree[i] = INF;
vis[i] = false;
}
dist_to_tree[1] = 0;
long long need = 0;
for (int i = 1; i <= tree_cnt; i++) {
int u = 0;
for (int j = 1; j <= tree_cnt; j++) {
if (vis[j]) {
continue;
}
if (u == 0 || dist_to_tree[j] < dist_to_tree[u]) {
u = j;
}
}
vis[u] = true;
need = max(need, dist_to_tree[u]);
for (int v = 1; v <= tree_cnt; v++) {
if (vis[v]) {
continue;
}
long long w = dis2(u, v);
if (w < dist_to_tree[v]) {
dist_to_tree[v] = w;
}
}
}
return need;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> monkey_cnt;
for (int i = 1; i <= monkey_cnt; i++) {
cin >> jump_len[i];
}
cin >> tree_cnt;
for (int i = 1; i <= tree_cnt; i++) {
cin >> x[i] >> y[i];
}
long long need = prim_need();
int answer = 0;
for (int i = 1; i <= monkey_cnt; i++) {
if (jump_len[i] * jump_len[i] >= need) {
answer++;
}
}
cout << answer << '\n';
return 0;
}复杂度
设树的数量为 N。
Prim 使用邻接矩阵式的在线更新，不显式存所有边：
- 时间复杂度
- 空间复杂度
总结
这题表面是在统计猴子，其实先要抽出一个图论核心问题：全图连通需要的最小单跳距离是多少。一旦把它识别成“最小生成树里的最大边”，后面就是一题很标准的 MST 变形。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
