AcWing 2724. 雷达 题解

题目分析

本题中爪哇王国的(N)个城市需要被雷达覆盖，王国有(M)个雷达站，但只有(K)个操作员，即最多只能操作(K)个雷达。所有雷达覆盖区域是以自身为圆心的圆形，且覆盖半径都为(R)。要求在使用不超过(K)个雷达的情况下，计算能使所有城市都被覆盖的(R)的最小值。

解题思路

本题采用二分查找结合舞蹈链（DLX）算法的方法。首先通过二分查找确定半径(R)的可能范围，对于每个二分得到的半径值(mid)，构建一个(0 - 1)矩阵，其中行代表雷达，列代表城市，若某个雷达在半径(mid)下能覆盖某个城市，则矩阵对应位置为(1)，否则为(0)。然后使用舞蹈链算法判断能否用不超过(K)个雷达（即选取不超过(K)行）覆盖所有城市（即每列恰好有一个(1)被选取），根据判断结果缩小二分查找的范围，最终得到(R)的最小值。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 55, M = N * N;

int n, m, k;
int l[M], r[M], u[M], d[M], row[M], col[M], s[M], idx;
bool st[N];
PDD city[N], station[N];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能。
• 使用宏定义x和y分别表示pair类型的第一个和第二个元素。
• 定义PDD类型为pair<double, double>，用于存储坐标。
• 定义常量(N)（最大城市数或雷达站数）和(M)（矩阵元素的最大数量）。
• 变量(n)表示城市数量，(m)表示雷达站数量，(k)表示最多可操作的雷达数量。
• l、r、u、d数组分别表示双向链表的左、右、上、下指针；row数组记录每个节点所在的行；col数组记录每个节点所在的列；s数组记录每列中(1)的个数；idx用于节点编号。
• st数组用于标记，在启发式函数中使用。

• city数组存储城市的坐标，station数组存储雷达站的坐标。

• 初始化函数

void init()
{
    for (int i = 0; i <= n; i ++ )
    {
        l[i] = i - 1, r[i] = i + 1;
        col[i] = u[i] = d[i] = i;
        s[i] = 0;
    }
    l[0] = n, r[n] = 0;
    idx = n + 1;
}

初始化双向链表，构建列头节点的双向循环链表，设置每列头节点的上下指针指向自身，左右指针构成循环，同时初始化每列的元素计数为(0)。设置头节点的左右指针构成循环，并初始化节点编号idx从(n + 1)开始。

1. 添加节点函数

void add(int& hh, int& tt, int x, int y)
{
    row[idx] = x, col[idx] = y, s[y] ++ ;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx ++ ;
}

向双向链表中添加一个节点。记录节点所在的行x和列y，增加列y中(1)的计数。在垂直方向上，将新节点插入到列头节点和原列中下方节点之间；在水平方向上，将新节点插入到当前行已有节点的末尾。最后更新行尾指针tt并递增节点编号idx。

1. 启发式函数

int h()
{
    int res = 0;
    memset(st, 0, sizeof st);
    for (int i = r[0]; i; i = r[i])
    {
        if (st[i]) continue;
        res ++ ;
        st[i] = true;
        for (int j = d[i]; j != i; j = d[j])
            for (int k = r[j]; k != j; k = r[k])
                st[col[k]] = true;
    }
    return res;
}

启发式函数，用于估算当前状态下还需要选取的最少行数。遍历每一列，若该列未被标记，标记该列并增加计数，同时标记该列中所有节点所在的列，最后返回计数结果。

1. 删除列函数

void remove(int p)
{
    for (int i = d[p]; i != p; i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}

删除指定列p及其相关的节点。遍历该列中的每个节点，将其从水平链表中移除。

1. 恢复列函数

void resume(int p)
{
    for (int i = u[p]; i != p; i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}

恢复之前删除的列p及其相关节点。遍历该列中的每个节点，将其重新插入到水平链表中。

1. 深度优先搜索函数

bool dfs(int k, int depth)
{
    if (k + h() > depth) return false;
    if (!r[0]) return true;
    int p = r[0];
    for (int i = r[0]; i; i = r[i])
        if (s[p] > s[i])
            p = i;

    for (int i = d[p]; i != p; i = d[i])
    {
        remove(i);
        for (int j = r[i]; j != i; j = r[j]) remove(j);
        if (dfs(k + 1, depth)) return true;
        for (int j = l[i]; j != i; j = l[j]) resume(j);
        resume(i);
    }

    return false;
}

深度优先搜索函数，用于寻找满足条件的最少行数。
- 如果当前已选取的行数加上启发式函数估算的最少还需选取的行数大于给定的深度depth，则返回false，表示该搜索路径不可行。
- 如果头节点的右指针指向自身（即(r[0] == 0)），说明所有列都已被覆盖，返回true。
- 选择当前列中元素个数最少的列p，遍历该列中的每个节点i，删除该节点及其所在行的所有节点，递归调用dfs继续搜索，如果找到解则返回true。若递归搜索失败，则恢复之前删除的节点。
- 如果所有节点都遍历完仍未找到解，则返回false。

1. 距离判断函数

bool check(PDD a, PDD b, double mid)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy <= mid * mid;
}

判断两个点（城市和雷达）之间的距离是否小于等于给定的半径mid，通过计算两点之间距离的平方与半径平方比较大小来实现。

1. 整体判断函数

bool check(double mid)
{
    init();
    for (int i = 1; i <= m; i ++ )
    {
        int hh = idx, tt = idx;
        for (int j = 1; j <= n; j ++ )
            if (check(station[i], city[j], mid))
                add(hh, tt, i, j);
    }

    int depth = 0;
    while (depth <= k && !dfs(0, depth)) depth ++ ;
    return depth <= k;
}

对于给定的半径mid，判断能否用不超过(K)个雷达覆盖所有城市。
- 初始化双向链表。
- 遍历所有雷达和城市，若某个雷达在半径mid下能覆盖某个城市，则在双向链表中添加对应节点。
- 从深度0开始，不断增加深度，调用dfs函数进行搜索，直到找到解或者深度超过(k)。如果最终深度小于等于(k)，则表示能用不超过(K)个雷达覆盖所有城市，返回true，否则返回false。

1. 主函数

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &city[i].x, &city[i].y);
        for (int i = 1; i <= m; i ++ ) scanf("%lf%lf", &station[i].x, &station[i].y);
        double l = 0, r = 2000;
        while (r - l > 1e-10)
        {
            double mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid;
        }
        printf("%lf\n", r);
    }
    return 0;
}

• 读取测试用例的数量T，对于每个测试用例：
  • 读取城市数量n、雷达站数量m和最多可操作的雷达数量k。
  • 读取所有城市和雷达站的坐标。
  • 初始化二分查找的范围，左边界l = 0，右边界r = 2000。
  • 进行二分查找，对于每个中间值mid，调用check函数判断能否用不超过(K)个雷达覆盖所有城市，根据判断结果更新二分查找的范围。
  • 最终输出满足条件的最小半径r。

时间复杂度分析

二分查找的时间复杂度为(O(log C))，其中(C)是半径的搜索范围。对于每个二分的半径值，构建双向链表和进行舞蹈链搜索的时间复杂度为指数级，但由于启发式函数的剪枝作用，实际平均时间复杂度会降低。整体时间复杂度近似为(O(log C \times 指数级时间))。

空间复杂度分析

主要空间消耗在于存储双向链表的各种数组、城市和雷达站的坐标数组以及标记数组st等，空间复杂度为(O(N^2)) 。