Airport HDU

The country of jiuye composed by N cites. Each city can be viewed as a point in a two- dimensional plane with integer coordinates (x,y). The distance between city i and city j is defined by d _ij = |x _i - x _j| + |y _i - y _j|. jiuye want to setup airport in K cities among N cities. So he need your help to choose these K cities, to minimize the maximum distance to the nearest airport of each city. That is , if we define d_i(1 ≤ i ≤ N ) as the distance from city i to the nearest city with airport. Your aim is to minimize the value max{d _i|1 ≤ i ≤ N }. You just output the minimum.

InputThe first line of the input is T (1 ≤ T ≤ 100), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,K (1 ≤ N ≤ 60,1 ≤ K ≤ N ),as mentioned above.

The next N lines, each lines contains two integer x _i and y _i (-10 ⁹ ≤ x _i, y _i ≤ 10 ⁹), denote the coordinates of city i.OutputFor each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then a single integer means the minimum.Sample Input

Sample Output

Case #1: 2
Case #2: 4

题意：有n块小岛，现在要在其中的k块小岛上建立飞机场，给出小岛的坐标，其中小岛之间的距离d(i,j)=|xi-xj|+|yi-yj|;求建立k个飞机时，飞机的最小航距时多少；

思路：二分法判断航距，用DLX重复覆盖判断当前航距下能否满足k座，最后一步步缩小答案。注意岛之间的距离非常大，用long long 存放。

代码：

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 const int maxn=4010;
 22 int k;
 23 struct 
 24 {
 25     int left[maxn],right[maxn],up[maxn],down[maxn];
 26     int head[65],col[maxn];
 27     int num[65],id;
 28     void init(int m)
 29     {
 30         for(int i=0;i<=m;i++)
 31         {
 32             left[i]=i-1;
 33             right[i]=i+1;
 34             up[i]=down[i]=i;
 35             col[i]=i;
 36         }
 37         id=m;
 38         left[0]=m;
 39         right[m]=0;
 40         memset(head,-1,sizeof(head));
 41         memset(num,0,sizeof(num));
 42     }
 43     void link(int x,int y)
 44     {
 45         id++;
 46         down[id]=down[y];
 47         up[down[y]]=id;
 48         up[id]=y;
 49         down[y]=id;
 50         num[y]++;
 51         col[id]=y;
 52         if(head[x]==-1)
 53         {
 54             head[x]=left[id]=right[id]=id;
 55         }
 56         else
 57         {
 58             right[id]=right[head[x]];
 59             left[right[head[x]]]=id;
 60             left[id]=head[x];
 61             right[head[x]]=id;
 62         }
 63     }
 64     void remove(int c)
 65     {
 66         for(int i=down[c];i!=c;i=down[i])
 67         {
 68             left[right[i]]=left[i];
 69             right[left[i]]=right[i];
 70         }
 71     }
 72     void reback(int c)
 73     {
 74         for(int i=up[c];i!=c;i=up[i])
 75         {
 76             left[right[i]]=right[left[i]]=i;
 77         }
 78     }
 79     bool bj[maxn];
 80     int A()
 81     {
 82         int ans=0;
 83         for(int c=right[0];c!=0;c=right[c])
 84         {
 85             bj[c]=true;
 86         }
 87         for(int c=right[0];c!=0;c=right[c])
 88         {
 89             if(bj[c])
 90             {
 91                 ans++;
 92                 bj[c]=false;
 93                 for(int i=down[c];i!=c;i=down[i])
 94                 {
 95                     for(int j=right[i];j!=i;j=right[j])
 96                     {
 97                         bj[col[j]]=false;
 98                     }
 99                 }
100             }
101         }
102         return ans;
103     }
104     bool danc(int step)
105     {
106         if(A()+step>k)//剪枝
107         {
108             return false;
109         }
110         if(right[0]==0)
111         {
112             return step<=k;
113         }
114         int c=right[0];
115         for(int i=c;i!=0;i=right[i])
116         {
117             if(num[i]<num[c])
118             {
119                 c=i;
120             }
121         }
122         for(int i=down[c];i!=c;i=down[i])
123         {
124             remove(i);
125             for(int j=right[i];j!=i;j=right[j])
126             {
127                 remove(j);
128             }
129             if(danc(step+1))
130             {
131                 return true;
132             }
133             for(int j=left[i];j!=i;j=left[j])
134             {
135                 reback(j);
136             }
137             reback(i);
138         }
139         return false;
140     }
141 }dlx;
142 struct node//小岛信息
143 {
144     ll x,y;
145 }no[65];
146 ll dis(node a,node b)//计算距离
147 {
148     ll dx=a.x-b.x;
149     if(dx<0)
150     {
151         dx=-dx;
152     }
153     ll dy=a.y-b.y;
154     if(dy<0)
155     {
156         dy=-dy;
157     }
158     return dx+dy;
159 }
160 int main()
161 {
162     int t,ans=0;;
163     scanf("%d",&t);
164     while(t--)
165     {
166         ans++;
167         int n;
168         ll x[65],y[65];
169         scanf("%d %d",&n,&k);
170         for(int i=1;i<=n;i++)
171         {
172             scanf("%lld %lld",&no[i].x,&no[i].y);
173         }
174         ll le=0,rig=100000000000LL;
175         while(rig-le>0)
176         {
177             dlx.init(n);
178             ll mid=(rig+le)/2;
179             for(int i=1;i<=n;i++)
180             {
181                 for(int j=1;j<=n;j++)
182                 {
183                     if(dis(no[i],no[j])<=mid)//岛之间的距离比航距小时
184                     {
185                         dlx.link(i,j);
186                     }
187                 }
188             }
189             if(dlx.danc(0))//如果当前航距需要的最少飞机的数量比k小为true
190             {
191                 rig=mid;
192             }
193             else
194             {
195                 le=mid+1;
196             }
197         }
198         printf("Case #%d: %lld
",ans,le);
199     }
200 }