洛谷OJ：P1991 无线通讯网_无线电通讯 oj 边防哨所卫星电话-CSDN博客

本文链接：https://blog.csdn.net/Elvis_code_t/article/details/80071016

该博客分析了洛谷OJ中P1991题目的解决方案，重点在于理解如何利用卫星电话线路连接哨所，形成联通块。通过贪心策略，选择最短边来构建生成树，并在确保所有哨所联通的情况下，记录最长的边，以解决当卫星电话数量有限时的最大通讯距离问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

分析：根据"任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远"和可安装的卫星电话的哨所数为s可知只需要将这些哨所连城s个联通块即可，所以只需要贪心将当前剩余最短的边加入生成树并记录生成树中最长的边至剩余s个联通块即可得出答案。

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

const int maxn = 500+10;
struct Edge{
    int f, t;
    double c;
    bool operator < ( Edge a ) const { return c < a.c; }
};
vector<Edge> es;
int par[maxn], rank_[maxn];
int n, m, last;
double x[maxn], y[maxn];
double ans;

double get_dis(double x1, double y1, double x2, double y2) {
    return sqrt( 1.0*(1.0*(x1-x2)*(x1-x2) + 1.0*(y1-y2)*(y1-y2)) );
}

void init(int n) { for(int i = 1; i <= n; i++) par[i] = i; }

int find_(int x) { return x == par[x] ? x : par[x] = find_(par[x]); }

bool same(int a, int b) { return find_(a) == find_(b); }

void unite(int a, int b) {
    a = find_(a); b = find_(b);
    if(a == b) return;
    if(rank_[b] > rank_[a])
        par[a] = b;
    else {
        par[b] = a;
        if(rank_[a] == rank_[b])
            rank_[a]++;
    }
}

void Krusal() {
    sort(es.begin(), es.end());
    Edge cur;
    for(int i = 0; i < es.size() && last > n; i++) {
        if(!same(es[i].f, es[i].t)) {
            last--;
            unite(es[i].f, es[i].t);
            ans = max(ans, es[i].c);
        }
    }
    int p = 0;

}

int main() {
    scanf("%d %d", &n, &m);
    init(m);
    last = m;
    for(int i = 1; i <= m; i++)
        cin >> x[i] >> y[i];
    double dis;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            if(i != j) {
                dis = get_dis((double)x[i], (double)y[i], (double)x[j], (double)y[j]);
                es.push_back(Edge{i, j, dis});
            }
        }
    }
    Krusal();
    printf("%.2lf\n", ans);
    return 0;
}