AcWing 1145. 北极通讯网络（最小生成树 | 克鲁斯卡尔算法与并查集）
发布时间
阅读量：
阅读量
AcWing 1145. 北极通讯网络
解题思路：无线通信的功能可以类比为将多个村落整合为相互连接的连通区域，而卫星的作用则是将这些连通区域进一步连接起来。通过并查集的数据结构来追踪连通区域的数量，初始状态下每个村落各自独立，因此连通区域的数量等于村落的总数。随着无线通信覆盖范围逐步扩大，连通区域的数量会随之减少。当连通区域的数量不超过卫星数量时，此时的通信距离即为满足题目要求的最小距离。
#include<bits/stdc++.h>
using namespace std;
#define db double
#define x first
#define y second
const int N = 520, M = N * N / 2;
typedef pair<int, int>PII;
struct Node{
int a, b;
db w;
bool operator< (const Node &t) const{
return w < t.w;
}
}de[M]; //这里储存的是边，全部评论 (0)
还没有任何评论哟~