程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2295 DLX 二分

HDU 2295 DLX 二分

編輯：C++入門知識

Radar

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2229 Accepted Submission(s): 888

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

有n個城市，m個發電站，已知他們的坐標，每個發電站覆蓋半徑相同，求多大半徑時可以把所有的城市都覆蓋，二分半徑建圖，dlx爆搜。

代碼：

/* ***********************************************
Author :_rabbit
Created Time :2014/4/28 14:08:33
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Point{
    double x,y;
}city[100],radar[100];
double dis[66][66];
double dist(Point a,Point b){
    double s=a.x-b.x,t=a.y-b.y;
    return s*s+t*t;
}
int K;
struct DLX{
    const static int maxn=20010;
    #define FF(i,A,s) for(int i = A[s];i != s;i = A[i])
    int L[maxn],R[maxn],U[maxn],D[maxn];
    int size,col[maxn],row[maxn],s[maxn],H[maxn];
    bool vis[70];
    int ans[maxn],cnt;
    void init(int m){
        for(int i=0;i<=m;i++){
            L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;
        }
        memset(H,-1,sizeof(H));
        L[0]=m;R[m]=0;size=m+1;
    }
    void link(int r,int c){
         U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;
         if(H[r]<0)H[r]=L[size]=R[size]=size;
         else {
             L[size]=H[r];R[size]=R[H[r]];
             L[R[H[r]]]=size;R[H[r]]=size;
         }
         s[c]++;col[size]=c;row[size]=r;size++;
     }
    void del(int c){//精確覆蓋
        L[R[c]]=L[c];R[L[c]]=R[c];  
        FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];  
    }  
    void add(int c){  //精確覆蓋
        R[L[c]]=L[R[c]]=c;  
        FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];  
    }  
    bool dfs(int k){//精確覆蓋
        if(!R[0]){  
            cnt=k;return 1;  
        }  
        int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;  
        del(c);  
        FF(i,D,c){  
            FF(j,R,i)del(col[j]);  
            ans[k]=row[i];if(dfs(k+1))return true;  
            FF(j,L,i)add(col[j]);  
        }  
        add(c);  
        return 0;
    }  
    void remove(int c){//重復覆蓋
        FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
    }
     void resume(int c){//重復覆蓋
         FF(i,U,c)L[R[i]]=R[L[i]]=i;
     }
    int A(){//估價函數
        int res=0;
        memset(vis,0,sizeof(vis));
        FF(i,R,0)if(!vis[i]){
                res++;vis[i]=1;
                FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
            }
        return res;
    }
    void dfs(int now,int &ans){//重復覆蓋
        if(R[0]==0)ans=min(ans,now);
        else if(now+A()s[i])temp=s[i],c=i;
            FF(i,D,c){
                remove(i);FF(j,R,i)remove(j);
                dfs(now+1,ans);
                FF(j,L,i)resume(j);resume(i);
            }
        }
    }
/*    int astar(){
        int lim=A();
        while(!dfs(0,lim))lim++;
        return lim;
    }*/
}dlx;
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int T,n,m;
     cin>>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",&radar[i].x,&radar[i].y);
         for(int i=1;i<=m;i++)
             for(int j=1;j<=n;j++)dis[i][j]=dist(radar[i],city[j]);
         double left=0,right=1500;
         while(right-left>1e-7){
             double mid=(left+right)/2;
             double ss=mid*mid;
             dlx.init(n);
             for(int i=1;i<=m;i++)
                 for(int j=1;j<=n;j++)
                     if(dis[i][j]<=ss)dlx.link(i,j);
        //     cout<