题解无线通讯网

Lee Wen

2025-04-06 18:09:28

发布于：广东

58阅读

0回复

0点赞

题解：无线通讯网

预备知识

1.并查集
2.最小生成树
3.坐标轴上两点距离公式

题意概述

这道题目算是最讨厌的“阅读理解”题目了它的题目挺长的所以化简能力在此显现了出来
抽象题目得出：

2种网络方式连接P个哨所
方式1.卫星电话
a.只有S台卫星电话
b.连接的两个哨所都要有卫星电话
c.卫星任意距离都可(解决相隔最远的)
方式2.无线电
a.连接的哨所距离不超过D
要求每个哨所都有一条通话路径(生成树)
目标：求得D的最小值

思路分析

关于求出两个哨所距离很简单：
直接即可 $D=\sqrt {(x_1-x_2)^2+(y_1-y_2)^2}$
明确一个观点对于一个哨所连接离他近的哨所肯定比连接远的更优
同时一个哨所我们肯定是只连接一个哨所就好(满足连通性)
很显然针对这样我们可以发现题目要求的就是找到最小的无向连通无环图
这不就是最小生成树嘛！

把这个坐标轴上所有的哨所连接就构成了原始图
在原始图的基础上求最小生成树(因为我们一开始不知道哪些边会去掉)
而后在最小生成树中找到最大的前 $(S/2)$ 条边用卫星电话代替
最小的传输距离：D=最大的前 $(S/2-1)$ 条边的长度
也就是相当于让已经取得的边数 $e$ 取到 $P-S$ 的时候结束
保存这个时候的长度即可

代码实现

#include <bits/stdc++.h>
#define rep_a(i,n) for(int i=1;i<=(n);i++) //正
#define rep_b(i,n) for(int i=n;i>=1;i--) //逆
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=2e5+5;
double ans;double fa[MAXN];
ll m;ll S,P;
struct EDGE{double u,v;double w;}edge[MAXN];//存边
struct NODE{double x,y;}node[MAXN];//存点
bool cmp(EDGE x,EDGE y){
	return x.w<y.w;
}
//———————————————————————————————以下为并查集初始化
void init(){//并查集初始化 单测
	rep_a(i,P){fa[i]=i;}
}
ll _get(ll x){
	if(x==fa[x]) return x;
	return fa[x]=_get(fa[x]);//递归找牢大 顺便重新定义牢大(最大的)
	//如上路径压缩优化O(n)->O(1) 深度最多为2
}
void merge(ll x,ll y){//合并关联x,y的两个集合
	ll fx=_get(x);
	ll fy=_get(y);
	if(fx!=fy){
		fa[fx]=fy;
	}
}
bool same(ll x,ll y){//判断x,y是否在一个集合里面
	if(_get(x)==_get(y)){return 1;}
	else{return 0;}
}
//——————————————————————————————————————
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>S>>P;
	init();
	int x_1,x_2,y_1,y_2;
	rep_a(i,P){
		cin>>node[i].x>>node[i].y;
		for(int j=1;j<i;j++){
			x_1=node[i].x;x_2=node[j].x;
			y_1=node[i].y;y_2=node[j].y;
			m++;
			edge[m].u=i;edge[m].v=j;
			edge[m].w=sqrt((x_1-x_2)*(x_1-x_2)*1.0+(y_1-y_2)*(y_1-y_2)*1.0);
		}
	}
	sort(edge+1,edge+m+1,cmp);
	ll e=0;//已经取了的边数
	rep_a(i,m){
		if(!same(edge[i].u,edge[i].v)){
			merge(edge[i].u,edge[i].v);
			ans=edge[i].w;
			e++;
			if(e>=P-S){
				printf("%.2lf",ans);
				return 0;
			}
		}
	}
	

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

天空之尽

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v;
    double w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};
struct UnionFind {
    vector<int> parent;
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }
};
int main() {
    int S, P;
    cin >> S >> P;
    vector<pair<int, int>> points(P);
    for (int i = 0; i < P; i++) {
        cin >> points[i].first >> points[i].second;
    }
    // 特殊情况：卫星电话足够多
    if (S >= P) {
        cout << "0.00" << endl;
        return 0;
    }
    // 计算所有边
    vector<Edge> edges;
    for (int i = 0; i < P; i++) {
        for (int j = i + 1; j < P; j++) {
            double dx = points[i].first - points[j].first;
            double dy = points[i].second - points[j].second;
            double dist = sqrt(dx * dx + dy * dy);
            edges.push_back({i, j, dist});
        }
    }
    // Kruskal求MST
    sort(edges.begin(), edges.end());
    UnionFind uf(P);
    vector<double> mstEdges; // 存储MST中的边权
    
    for (const auto& e : edges) {
        if (uf.unite(e.u, e.v)) {
            mstEdges.push_back(e.w);
            if (mstEdges.size() == P - 1) break;
        }
    }
    // 答案：MST中第 (P-S) 条边（0-indexed是P-S-1），即第S大的边
    // 从小到大排序后，去掉最大的S-1条，剩下最大的就是第(P-S)个
    sort(mstEdges.begin(), mstEdges.end());
    double ans = mstEdges[P - S - 1];
    cout << fixed << setprecision(2) << ans;
    return 0;
}

2026-03-25 来自江苏

‌jamesshao
kook

2025-07-10 来自上海
0