洛谷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 = ;

const int M = ;

int mok[N], cnt, n, m, num = , fa[M], ans, X[M], Y[M];

double sum = -0x3f3f3f3f;

struct node {

    int x, y;

    double dis;

}e[M];

int read() {

    int s = , w = ;

    char ch = getchar();

    while(!isdigit(ch)) {if(ch == '-') w = -; ch = getchar();}

    while(isdigit(ch)) {s = s *  + ch - ''; 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 = ; i <= n; i++) mok[i] = read();

    m = read();

    for(int i = ; i <= m; i++) X[i] = read(), Y[i] = read();

    for(int i = ; i <= m; i++)

        for(int j = i + ; j <= m; j++)

            e[++cnt].x = i, e[cnt].y = j, e[cnt].dis = way(i, j);

    sort(e + , e +  + cnt, cmp);

    for(int i = ; i <= m; i++) fa[i] = i;

    for(int i = ; 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 = ; i <= n; i++) if(mok[i] >= sum) ans++;

    printf("%d\n", ans);

    return ;

}

谢谢收看， 祝身体健康！