P1991 无线通讯网题解

Author: Yuyi

题意分析

题意可以转化为：给定 $P$ 个哨所（可以看作平面上的 $P$ 个点），我们要在任意两点之间连一条边，边的权值为这两点之间的欧几里得距离。现在我们手里有 $S$ 个“卫星电话”。拥有卫星电话的哨所之间互相通信是“免费”的（距离不受限）。这意味着这 $S$ 个分配了卫星电话的哨所，等价于允许整个图存在 $S$ 个互不连通的“连通块”而依然能互相通信。题目要求所有普通无线电收发器的最大距离 $D$ 尽量小。这不就是妥妥的 Kruskal 最小生成树 变种吗！我们只需要将所有边按权值从小到大排序，当连通块数量刚好降到 $S$ 的时候，最后加进来的那条边的权值就是我们要求的 $D$ 。

正解推导过程

由于任何两个哨所都可以用无线电相连，我们首先需要构建一张完全图：

建图：枚举所有的点对 $(i, j)$ ，计算它们之间的直线距离，存入边集数组中。边数总共约 $\frac{P(P-1)}{2} \approx 1.25 \times 10^5$ 条。
Kruskal 贪心加边：将所有的边按权值从小到大排序。
并查集维护连通块：起初有 $P$ 个节点，也就是 $P$ 个独立的连通块。每次通过并查集 find 找到两个端点，如果不在同一个连通块，就合并它们。合并一次，整个图的连通块数量就会减一。
结束条件：起初连通块个数为 $P$ ，要让连通块个数降到 $S$ ，我们恰好需要成功加入 $P - S$ 条边。加入的第 $P - S$ 条边，就是我们所需的最长无线电通信距离 $D$ 。

正解代码及分析

#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)$ ；然后对最多 $\frac{P^2}{2}$ 条边进行排序，耗时约 $O(P^2 \log P)$ ；最后使用并查集扫描边合并，因为路径压缩的存在几乎是线性的 $O(P^2)$ 。综合来看时间复杂度为 $O(P^2 \log P)$ ，在 $P \le 500$ 面前毫无压力。

另一种解法：二分答案 + 并查集检验

这道题确实可以直接用二分来做！因为“使得每一对哨所之间至少有一条通话路径的最短收发器距离 $D$ ”是一个极其典型的最大值最小化问题，具有单调性：如果距离 $D$ 能够满足要求，那么所有比 $D$ 大的距离一定也都满足；如果 $D$ 不满足，所有比 $D$ 小的距离更不满足。

二分边界：距离最小是 $0$ ，最大是网格对角线大约 $10000 \times \sqrt{2} \approx 14142.2$ 。我们直接在 $[0, 20000]$ 范围内二分实数 $D$ 。
check(mid) 函数设计：对于给定的距离上限 mid，我们遍历所有点对。如果两点之间的距离 $\le mid$ ，就用并查集将它们合并。由于起初有 $P$ 个独立连通块，每次成功合并就让连通块数量 cnt--。最后检查 cnt 是否 $\le S$ 即可。如果剩下的连通块数量 $\le S$ ，说明借用 $S$ 个卫星电话足以连通全局，这个 mid 是可行的。

法二代码及分析

#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 = 505; // 二分法不存边，仅存点即可
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];
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
bool check(double mid)
{
    rep(i,1,p) fa[i] = i;
    int cnt = p;
    rep(i,1,p)
    {
        rep(j,i+1,p)
        {
            double dist = sqrt((double)(x[i]-x[j])*(x[i]-x[j]) + (double)(y[i]-y[j])*(y[i]-y[j]));
            if(dist <= mid)
            {
                int fu = find(i);
                int fv = find(j);
                if(fu != fv)
                {
                    fa[fu] = fv;
                    cnt--;
                }
            }
        }
    }
    return cnt <= s;
}
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;
    }
    double l = 0, r = 20000.0;
    while(r - l > eps) // 满足精度eps = 1e-9后退出
    {
        double mid = (l + r) / 2.0;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(2) << r << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

二分法复杂度：二分实数在 eps = 1e-9 精度下，循环大约需要跑 $50 \sim 60$ 次。每次 check 需要 $O(P^2)$ 的时间去双重循环判断点对，耗时约 $1.25 \times 10^5$ 次。综合时间复杂度为 $O(k \cdot P^2)$ （ $k$ 为常数 $60$ ），运算量约 $7.5 \times 10^6$ ，与 Kruskal 的 $O(P^2 \log P)$ 不相上下，同样能稳妥 AC。而且二分法不需要提前把所有边存下来，空间复杂度仅为 $O(P)$ ，连数组都可以放心降到 maxn = 505！

无线通讯网

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

数据范围及约定

🚀 提交评测

💡 题解 (1)

P1991 无线通讯网题解

题意分析

正解推导过程

正解代码及分析

复杂度分析

另一种解法：二分答案 + 并查集检验

法二代码及分析

💬 题目讨论 (0)

📊 题目信息

⚡ 快速操作

无线通讯网

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

数据范围及约定

🚀 提交评测

💡 题解 (1)

P1991 无线通讯网 题解

题意分析

正解推导过程

正解代码及分析

复杂度分析

另一种解法：二分答案 + 并查集检验

法二代码及分析

💬 题目讨论 (0)

📊 题目信息

⚡ 快速操作

P1991 无线通讯网题解