P2504 Kruskal全RE 求帮助
  • 板块学术版
  • 楼主Prolystic
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/12/29 16:30
  • 上次更新2023/12/29 19:59:30
查看原帖
P2504 Kruskal全RE 求帮助
695863
Prolystic楼主2023/12/29 16:30
#include <bits/stdc++.h>
using namespace std;
// 快读
inline 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;
}
inline void write(int x){
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
// 获取两个点的距离
inline double get_dist(int x_1, int y_1, int x_2, int y_2){
    int d_x = abs(x_1 - x_2), d_y = abs(y_1 - y_2);
    return sqrt((double)(d_x * d_x + d_y * d_y));
}
const int N_1 = 505, N_2 = 1005, M = 1e7 + 5;
struct Edge{
    int u, v; double w;
    bool operator <(Edge other){
        w < other.w;
    }
};
Edge e[M];
int fa[N_2]; // 并查集
int x[N_2], y[N_2]; // 树的坐标
int dis[N_1]; // 每一只猴子可以跳出的距离
int m, n, e_cnt, ans; // e_cnt 记录边数,ans是最小生成树上最长边的长度
// m 是猴子的数量,n 是树的数量
// 维护并查集
inline int find(int x){
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
// 初始化并查集
inline void init(){
    for(int i = 1; i <= n; i++)
        fa[i] = i;
}
// Kruskal
int kruskal(){
    int cnt = 0, mx = INT_MIN; // mx 记录最小生成树上最长边长度
    // cnt 记录目前已经加入最小生成树的边的数量
    // 循环
    for(int i = 1; i <= e_cnt; i++){ 
        int u = e[i].u, v = e[i].v, w = e[i].w;
        // 加入
        if(find(u) != find(v)){
            fa[find(u)] = find(v);
            cnt++;
            mx = max(mx, w);
        }
        // 如果已经满足一棵树的性质,那么退出
        if(cnt == n - 1)
            break;
    }
    return mx;
}
int main(){
    m = read();
    for(int i = 1; i <= m; i++)
        dis[i] = read();
    n = read();
    init();
    for(int i = 1; i <= n; i++)
        x[i] = read(), y[i] = read();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i != j){
                e_cnt++;
                e[e_cnt].u = i, e[e_cnt].v = j;
                e[e_cnt].w = get_dist(x[i], y[i], x[j], y[j]);
            }
        }
    }
    sort(e + 1, e + e_cnt + 1);
    int mx_w = kruskal();
    for(int i = 1; i <= m; i++)
        ans += (dis[i] >= mx_w);
    write(ans);
    return 0;
}
2023/12/29 16:30
加载中...