洛谷P2504 [HAOI2006]聪明的猴子题解

题目

 记录悲伤

已知猴子的数量以及猴子跳的最大距离

已知数的数量以及树的坐标

最小生成树

每两棵树之间的距离需要枚举来计算

算出最大值之后再与n只猴子进行比较记录答案

需要注意

在使用最小生成树的时候

我们的fa数组是记录的边他存储的是一棵树

结构体存储的信息也是一棵树

最后判断是否已经构成一棵树时

判断的是与m的大小关系

Code：

//I'll knock your block off if you break you word!
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5100;
const int M = 1000010;
int mok[N], cnt, n, m, num = 1, fa[M], ans, X[M], Y[M];
double sum = -0x3f3f3f3f;
struct node {
    int x, y;
    double dis;
}e[M];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
double way(int i, int j) {
    return sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));
}
bool cmp(node x, node y) {
    return x.dis < y.dis;
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
    n = read();
    for(int i = 1; i <= n; i++) mok[i] = read();
    m = read();
    for(int i = 1; i <= m; i++) X[i] = read(), Y[i] = read();
    for(int i = 1; i <= m; i++)
        for(int j = i + 1; j <= m; j++)
            e[++cnt].x = i, e[cnt].y = j, e[cnt].dis = way(i, j);
    sort(e + 1, e + 1 + cnt, cmp);
    for(int i = 1; i <= m; i++) fa[i] = i;
    for(int i = 1; i <= cnt; i++) {
        int fx = find(e[i].x), fy = find(e[i].y);
        if(fx != fy) {
            fa[fx] = fy;
            num++;
            sum = max(sum, e[i].dis);
//            cout << sum << endl;
        }
        if(num == m) break;
    }
    for(int i = 1; i <= n; i++) if(mok[i] >= sum) ans++;
    printf("%d\n", ans);
    return 0;
}

谢谢收看， 祝身体健康！