[Luogu]P1991 无线通讯网
本文最后更新于 287 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp1991/

题意

题目传送门

给出若干点,定义距离小于 $D$ 的点可以归于一个集合,可以强行将 $S$ 个点归于一个集合,求所有点在同一个集合时 $D$ 的最小值。

解法

主流的题解都是使用最小生成树的解法。
但笔者是从并查集题单来的,而且习惯用 prim 写最小生成树,因此就打了个并查集的做法。
正确性应该更好证明、更好思考。

要求某值最小,常规套路是二分
考虑二分 $D$ 的值,但距离值是浮点数,无法使用常规整数域二分。
可以预处理出所有点间的距离,去重排序后生成一个 $D$ 的数组,二分数组的下标。

在确认 $D$ 的情况下,考虑如何检验。
显然两点距离小于 $D$ 的可以归于一个集合,用并查集来处理。
若处理后只剩下一个集合,则合法。
若处理后剩余多个集合,考虑在两个集合之间增加卫星电话,这样该两个集合也并为一个。
那么消耗卫星电话数量即为集合数。(起点、终点都需要设置卫星电话)

检验的复杂度是 $O(n^2)$ 的,总复杂度为 $O(n^2 \log n)$,可以通过。

代码

代码实现也非常简单,就是一个二分板子套上一个并查集板子。

#include <cstdio>
#include <cmath>
#include <algorithm>
template <typename T>
void read(T &r)
{
    static char c;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxp = 510;
int s, p;
int X[maxp], Y[maxp];
double dis[maxp][maxp];
double D[maxp * maxp];
int tot;
int fa[maxp];
int find(const int &x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void unite(const int &a, const int &b)
{
    int x = find(a), y = find(b);
    if (x == y)
        return;
    fa[x] = y;
}
inline bool check(double d)
{
    for (int i = 1; i <= p; ++i)
        fa[i] = i;
    for (int i = 1; i <= p; ++i)
        for (int j = i + 1; j <= p; ++j)
            if (dis[i][j] <= d)
                unite(i, j);
    int num = 0;
    for (int i = 1; i <= p; ++i)
        if (find(i) == i)
            ++num;
    if (num == 1)
        return true;
    return tree <= s;
}
int main()
{
    read(s);
    read(p);
    for (int i = 1; i <= p; ++i)
        read(X[i]), read(Y[i]);
    for (int i = 1; i <= p; ++i)
        for (int j = i + 1; j <= p; ++j)
            dis[i][j] = dis[j][i] = std::sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])), D[++tot] = dis[i][j];
    std::sort(D + 1, D + 1 + tot);
    tot = std::unique(D + 1, D + 1 + tot) - D;
    int l = 1, r = tot, mid, ans;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(D[mid]))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    printf("%.2f", D[ans]);
    return 0;
}
本文标题:[Luogu]P1991 无线通讯网
本文作者:Clouder
本文链接: https://www.codein.icu/lp1991/
转载请标明。

评论

  1. 9月前
    2020-4-18 6:33:15

    tql,完全哇咔奶

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇