UVA10369 Arctic Network 题解

Author: Yuyi

题意分析

本题完全就是 P1991 无线通讯网 的国际原版！题目意思、条件限制甚至数据范围和核心要求都如出一辙：在 $P$ 个坐标点中连边，拥有 $S$ 个能够无视距离的“卫星频道”。我们要找到一个最小的通用收发器距离 $D$ ，使得在这 $D$ 距离内连边后，借助这 $S$ 个卫星频道，所有点依然能互相通信。唯一不同的是，本题是多组测试数据（Multiple Test Cases）。

正解推导过程

和上一题完全相同的 Kruskal 最小生成树 变种思路：

构建完全图：将每两点之间的欧几里得距离算出并建边。
Kruskal 连边：按边权从小到大加边，利用并查集维护连通性。
结束判定：初始时 $P$ 个点就是 $P$ 个连通块，每次成功加边会让连通块数减一。当刚好加入 $P-S$ 条边时，图内正好剩下 $S$ 个连通块。因为 $S$ 个卫星频道能将这 $S$ 个独立的连通块“免费”连通，此时刚加进去的那条边的权值就是我们的最小距离 $D$ 。
多测清空：由于每次循环都会重新读取 $P$ 和 $S$ ，并且重新累加生成边数 $m$ ，同时覆盖写入 e 数组和 fa 数组，因此本题极其纯净，不需要刻意 memset，直接解除主函数里 read(T) 的注释即可通杀。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 125005; // P<=500，最大边数约为125000，统一采用maxn开辟
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int s,p;
int x[maxn],y[maxn];
struct Edge
{
    int u,v;
    double w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void solve()
{
    read(s),read(p);
    rep(i,1,p) read(x[i]),read(y[i]);
    if(s >= p)
    {
        cout << fixed << setprecision(2) << 0.00 << endl;
        return;
    }
    int m = 0;
    rep(i,1,p)
    {
        rep(j,i+1,p)
        {
            m++;
            e[m].u = i;
            e[m].v = j;
            e[m].w = sqrt((double)(x[i]-x[j])*(x[i]-x[j]) + (double)(y[i]-y[j])*(y[i]-y[j]));
        }
    }
    rep(i,1,p) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    double ans = 0;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans = e[i].w; 
            cnt++;
        }
        if(cnt == p-s) break;
    }
    cout << fixed << setprecision(2) << ans << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
    read(T); // 此题为多组测试数据，直接解除注释即可完美运行！
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：计算所有点对之间的距离需 $O(P^2)$ ；随后对生成的 $M \le 125000$ 条边进行排序耗时 $O(P^2 \log P)$ ；最后并查集的合并时间复杂度接近 $O(P^2)$ 。综合来看单次测试用例的时间复杂度为 $O(P^2 \log P)$ ，即便处于多组数据（Multi-Testcases）的环境下，这套解法依然能飞速运行不超时。
空间复杂度：由于所有主要数组包括坐标数组 x、y 以及并查集和边集数组均严格采用统一的 maxn = 125005 进行定义和开辟，空间只受到最大边数的限制。总内存耗费不到 3MB，极度安全，完全杜绝 MLE 风险。

Arctic Network

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

题解

UVA10369 Arctic Network 题解

题意分析

正解推导过程

正解代码及分析

复杂度分析

讨论