程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2295 Radar（DLX可重復覆蓋）

HDU 2295 Radar（DLX可重復覆蓋）

編輯：C++入門知識

HDU 2295 Radar（DLX可重復覆蓋）

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 題意：n個城市，m個雷達站，最多用k個雷達站，問你每個雷達站的覆蓋半徑最少為多少。DLX可重復覆蓋做法：我們可以考慮以m個雷達站為N,以n個城市為M做成 DLX的可重復覆蓋模型。那麼N*M的bool值有如何確定了，我們考慮二分半徑r，對於每次二分的半徑r，我們在根據距離求出bool矩陣的0和1，然後就是DLX的可重復覆蓋模型。值得注意由於最多不超過k個雷達站，也是重要剪枝。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int maxn = 55;
const int maxnnode=maxn*maxn;
const int mod = 1000000007;
const double eps=1e-8;
int K;
struct DLX{
    int n,m,size;
    int U[maxnnode],D[maxnnode],L[maxnnode],R[maxnnode],Row[maxnnode],Col[maxnnode];
    int H[maxn],S[maxn];//H[i]位置，S[i]個數
    int ansd,ans[maxn];
    void init(int a,int b)
    {
        n=a;  m=b;
        REPF(i,0,m)
        {
            S[i]=0;
            U[i]=D[i]=i;
            L[i]=i-1;
            R[i]=i+1;
        }
        R[m]=0; L[0]=m;
        size=m;
        REPF(i,1,n)
           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[maxnnode];
    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(R[0] == 0)return d <= K;
        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;
    }
};
struct point{
    int x,y;
}X[maxn],Y[maxn];
DLX L;
int T,N,M;
double dis(point a,point b)
{
    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
void solve()
{
    double l=0,r=1e8;
    while(r-l>=eps)
    {
        double mid=(l+r)/2;
        L.init(M,N);
        for(int i=1;i<=M;i++)
        {
            for(int j=1;j<=N;j++)
            {
                if(dis(X[i],Y[j])






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

1
3 3 2
3 4
3 1
5 4
1 1
2 2
3 3


 



Sample Output

2.236068


 



Source

The 4th Baidu Cup final