雷达问题

解题思路

本题要取一个最小的雷达半径，使得我们从所有雷达中选 $k$ 个雷达能够将所有城市覆盖。

可以发现答案是具有单调性的，我们取的雷达半径越大，则我们选择的雷达数量就会越少。因此可以用二分来做，每次二分出一个雷达半径 $mid$，看一下在这个半径下最少要选多少个雷达才能覆盖所有城市，如果此时的雷达数量 $\leq k$，说明此时答案一定 $\leq mid$，则继续二分左区间。如果此时雷达的数量 $> k$，说明此时答案一定 $> mid$，则继续二分右区间。最终二分出一个固定值就是雷达半径的最小值。

剩下的问题就是，当每次确定雷达半径后，如何求出至少需要多少个雷达才能覆盖所有城市，这里可以转化成重复覆盖问题来做。

首先确定行，也就是选法，这里显然就是选择哪一个雷达，每一行分别对应一个雷达。然后考虑列，也就是限制，我们的目标是覆盖所有城市，因此每一列可以对应一个城市。对于每一行，将这个雷达能覆盖的每个城市对应的列记为 $1$。这样问题就变成了选出哪些行使得每一列都有 $1$（都被覆盖）。显然原问题中任意一种方案都能对应到重复覆盖问题中的任意一种方案。因此直接用 $Dancing~Links$ 直接求即可。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

const int N = 55, M = N * N;

int n, m, k;
//l[i] 表示节点 i 的左节点
//r[i] 表示节点 i 的右节点
//u[i] 表示节点 i 的上节点
//d[i] 表示节点 i 的下节点
//s[i] 表示第 i 列中 1 的个数
//row[i] 表示节点 i 所在的行的编号
//col[i] 表示节点 i 所在的列的编号
int l[M], r[M], u[M], d[M], s[M], row[M], col[M], idx;
bool st[N]; //判重数组
PDD city[N], station[N]; //城市、雷达站的坐标

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;
}

void add(int &hh, int &tt, int x, int y) //将 (x, y) 加入 hh 和 tt 之间
{
    row[idx] = x, col[idx] = y, s[y]++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = idx, l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx++;
}

int h() //估价函数
{
    int cnt = 0;
    memset(st, 0, sizeof st);
    for(int i = r[0]; i; i = r[i])
    {
        if(st[i]) continue;
        st[i] = true;
        cnt++;
        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 cnt;
}

void remove(int p) //删除第 p 列
{
    for(int i = d[p]; i != p; i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}

void resume(int p) //恢复第 p 列
{
    for(int i = u[p]; i != p; i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}

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[i] < s[p])
            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;
}

bool check(PDD a, PDD b, double mid) //判断半径为 mid 的雷达 a 能否覆盖城市 b
{
    double x = a.first - b.first;
    double y = a.second - b.second;
    return x * x + y * y <= mid * mid;
}

bool check(double mid) //判断雷达半径为 mid 时能否用 k 个雷达覆盖所有城市
{
    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;
}

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].first, &city[i].second);
        for(int i = 1; i <= m; i++) scanf("%lf%lf", &station[i].first, &station[i].second);

        //浮点数二分
        double l = 0, r = 2000;
        while(r - l > 1e-10)
        {
            double mid = (l + r) / 2;
            if(check(mid)) r = mid; //二分左区间
            else l = mid; //二分右区间
        }
        printf("%.6lf\n", r);
    }
    return 0;
}