HDU 2295 Radar (DLX + binary search)

Description

N个城市，共M处布有雷达，条件受限，这M处雷达只能选用K个去覆盖城市，求雷达最小覆盖半径

建模

Dancing-Links-X

行：可选解决方案——那些雷达

列：目标覆盖区域——那些城市

二分查找半径，判断：如果第i个雷达在此半径下能覆盖第j个城市，那么link(i, j)，问题转换为DLX重复覆盖：选取一些行，使得每列含有1

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxnode = 3005;
const double eps = 1e-8;

int n, m, k;

struct node
{
    double x, y;
};
node city[55], radar[55];
int cnt[55], Head[55], vis[55];
int L[maxnode], R[maxnode], U[maxnode], D[maxnode];
int Row[maxnode], Col[maxnode];

bool check(int i, int j, double dis)
{
    if((city[i].x - radar[j].x) * (city[i].x - radar[j].x) + (city[i].y - radar[j].y) * (city[i].y - radar[j].y) < dis * dis)
        return true;
    return false;
}

void init()
{
    for(int i = 0; i <= n; ++i)///列表元素
    {
        cnt[i] = 0;
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = D[i] = i;
    }
    L[0] = n;
    R[n] = 0;
    memset(Head, -1, sizeof(Head));
}

void link(int row, int col, int id)
{
    Row[id] = row;
    Col[id] = col;

    U[id] = U[col];
    D[id] = col;
    D[ U[col] ] = id;
    U[col] = id;

    if(Head[row] == -1)
        Head[row] = L[id] = R[id] = id;
    else
    {
        L[id] = L[ Head[row] ];
        R[id] = Head[row];
        R[ L[ Head[row] ] ] = id;
        L[ Head[row] ] = id;
    }

    cnt[col]++;
}

///具体删除列
void abandon(int id)
{
    for(int i = D[id]; i != id; i = D[i])
        L[ R[i] ] = L[i], R[ L[i] ] = R[i];
}

void resume(int id)
{
    for(int i = D[id]; i != id; i = D[i])
        L[ R[i] ] = R[ L[i] ] = i;
}

int h()
{
    int num = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = R[0]; i != 0; i = R[i])
    {
        if(!vis[i])
        {
            num++;
            for(int j = D[i]; j != i; j = D[j])
                for(int k = R[j]; k != j; k = R[k])
                    vis[ Col[k] ] = 1;
        }
    }
    return num;
}

bool Dance(int deep)
{
    if(deep + h() > k)
        return 0;

    if(R[0] == 0)
    {
        if(deep <= k)
            return 1;
        return 0;
    }

    int c = R[0];
    for(int i = R[0]; i != 0; i = R[i])
        if(cnt[i] < cnt[c])
            c = i;

    for(int i = D[c]; i != c; i = D[i])
    {
        abandon(i);///参数为id 我选这个1,后续无需参考此列(删除)
        for(int j = R[i]; j != i; j = R[j])
            abandon(j);///删除1元素所在行上 1元素所在列
        if(Dance(deep + 1))
            return 1;
        for(int j = R[i]; j != i; j = R[j])
            resume(j);
        resume(i);
    }
    return 0;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        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", &radar[i].x, &radar[i].y);

        double L = 0, R = 2000;
        while(R - L > eps)
        {
            double mid = (R + L) / 2.0;

            init();
            int id = n;
            for(int i = 1; i <= n; ++i)///列Col
                for(int j = 1; j <= m; ++j)///行Row
                {
                    if(check(i, j, mid))
                        link(j, i, ++id);
                }
            if(Dance(0))
                R = mid;
            else
                L = mid;
        }
        printf("%.6f\n", R);
    }
    return 0;
}