[ACM] HDU 2295 Radar (二分法+DLX 重复覆盖）

Radar

Problem Description

N cities of the Java Kingdom need to be covered by radars for being in a state of war. Since the kingdom has M radar stations but only K operators, we can at most operate K radars. All radars have the same circular coverage with a radius of R. Our goal is to minimize R while covering the entire city with no more than K radars.

Input

The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases. The first line of each test case consists of 3 integers: N, M, K, representing the number of cities, the number of radar stations and the number of operators. Each of the following N lines consists of the coordinate of a city.
Each of the last M lines consists of the coordinate of a radar station.

All coordinates are separated by one space.
Technical Specification

1. 1 ≤ T ≤ 20
2. 1 ≤ N, M ≤ 50
3. 1 ≤ K ≤ M
4. 0 ≤ X, Y ≤ 1000

Output

For each test case, output the radius on a single line, rounded to six fractional digits.

Sample Input

Sample Output

2.236068

Source

The 4th Baidu Cup final

解题思路：

题意为有m个雷达，每一个雷达的覆盖范围都为以r为半径的圆，给定他们的坐标，有n个城市。给定他们的坐标，求最小的r，使得每一个城市都被雷达覆盖。限制条件为最多仅仅有k个雷达工作。

二分答案r。推断所须要的雷达数是否小于给定的k，找到最小的r。

用Dlx反复覆盖来推断。首先建图：m行,n列的矩形，也就是横坐标代表雷达。纵坐标代表城市，假设雷达与城市之间的距离小于等于当前的r,则坐标处标记为1。否则为0，这样就转化为了01矩阵，也就是解决这个问题能不能在这个矩阵中找出一些行（行数小于等于k)，使得这些行组成的新矩阵，每列都至少有一个1（反复覆盖。每列能够有多个1）.

注意maxnode的范围，最大不能仅仅是 n*m, 列头结点还得加上即 n*m+m

关于精确覆盖和反复覆盖，以下转载于：http://www.cnblogs.com/jh818012/p/3252154.html

精确覆盖：
首先选择当前要覆盖的列(含1最少的列)。将该列和可以覆盖到该列的行所有去掉，再枚举加入的方法。
枚举某一行r，如果它是解集中的一个，那么该行所能覆盖到的全部列都不必再搜，所以删除该行覆盖到的全部列，又因为去掉的列相当于有解，所以可以覆盖到这些列的行也不用再搜，删之。

反复覆盖：
首先选择当前要覆盖的列(同上)，将该列删除，枚举覆盖到该列的全部行：对于某一行r，如果它是解集中的一个。那么该行所能覆盖到的列都不必再搜。所以删除该行覆盖到的全部列。
注意此时不用删去覆盖到这些列的行，由于一列中同意有多个1。
这里有一个A*的优化：估价函数h意义为从当前状态最好情况下须要加入几条边才干覆盖。

代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=52;
const int maxm=52;
const int maxnode=3020;
int n,m,k;

struct DLX
{
    int n,m,size;
    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
    int H[maxn],S[maxn];
    int ansd,ans[maxn];

    void init(int _n,int _m)
    {
        n=_n;
        m=_m;
        for(int i=0;i<=m;i++)
        {
            S[i]=0;
            U[i]=D[i]=i;
            L[i]=i-1;
            R[i]=i+1;
        }
        R[m]=0,L[0]=m;
        size=m;
        for(int i=1;i<=n;i++)
            H[i]=-1;
    }

    void link(int r,int c)
    {
        ++S[Col[++size]=c];
        Row[size]=r;
        D[size]=D[c];
        U[D[c]]=size;
        U[size]=c;
        D[c]=size;
        if(H[r]<0)
            H[r]=L[size]=R[size]=size;
        else
        {
            R[size]=R[H[r]];
            L[R[H[r]]]=size;
            L[size]=H[r];
            R[H[r]]=size;
        }
    }

    void remove(int c)
    {
        for(int i=D[c];i!=c;i=D[i])
            L[R[i]]=L[i],R[L[i]]=R[i];
    }

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

    bool v[maxnode];

    int f()//精确覆盖区估算剪枝
    {
        int ret=0;
        for(int c=R[0];c!=0;c=R[c])
            v[c]=true;
        for(int c=R[0];c!=0;c=R[c])
            if(v[c])
        {
            ret++;
            v[c]=false;
            for(int i=D[c];i!=c;i=D[i])
                for(int j=R[i];j!=i;j=R[j])
                v[Col[j]]=false;
        }
        return ret;
    }

    bool dance(int d)
    {
        if(d+f()>k)
            return false;
        if(d>k)
            return false;
        if(R[0]==0)
            return true;
        int c=R[0];
        for(int i=R[0];i!=0;i=R[i])
            if(S[i]<S[c])
            c=i;
        for(int i=D[c];i!=c;i=D[i])
        {
            remove(i);
            for(int j=R[i];j!=i;j=R[j])
                remove(j);
            if(dance(d+1)) return true;
            for(int j=L[i];j!=i;j=L[j])
                resume(j);
            resume(i);
        }
        return false;
    }
};


DLX g;
const double eps=1e-8;

struct point
{
    double x,y;
}city[maxm],radar[maxn];

double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&m,&n,&k);
        for(int i=1;i<=m;i++)
            scanf("%lf%lf",&city[i].x,&city[i].y);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&radar[i].x,&radar[i].y);
         double l=0,r=1e5;
        while(r-l>=eps)
        {
            double mid=(l+r)/2.0;
            g.init(n,m);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    if(dis(radar[i],city[j])<mid-eps)
                    g.link(i,j);
            if(g.dance(0))
                r=mid-eps;
            else
                l=mid+eps;
        }
        printf("%.6lf
",l);
    }
    return 0;
}