下面的代码99％参考了这个网站http://www.cnblogs.com/183zyz/archive/2011/08/07/2130193.html
人生的第一道DLX肯定是需要作一些参考的啦。
题意：给你N个城市，M个雷达，你要在其中选K个，问当半径最小是多少的时候可以覆盖到所有的N个城市。
做法：二分所需要的半径r,然后处理出这时雷达能够覆盖到哪些位置。然后就转化成了一个重复覆盖问题，跑一下DLX即可。
花了两天的时间学习了一下DLX这种神奇的数据结构,它在解决精确覆盖问题上尤其有帮助，因为随着每次选的一行，对应的包含了这个行的列的行也不会再用到，所以整个图会很快的变得非常小，从而可以极大得加快搜索速度。但是重复覆盖就没有缩小得那么快，包含了对应的列的行是不会消除掉的。
下面对模板的一些数组说下理解 L,R,U,D就是链表的四个方向,其中H是行的头指针，当该行不存在东西的时候H[]=-1,而col[size]表示结点编号为size所在的是哪一列，在精确覆盖的时候还要多维护一个row[size]去表示是在哪一行。对应的link函数是用来加条件的，然后dance就是递归，remove和resume则是对应的删除和恢复，在重复覆盖和精确覆盖问题上这两个操作要做相应的修改。
题目了用了个A*，多亏我有数据结构大作业的基础，A*就是在搜的时候多了个估价函数，但是这个估价函数必须保证不能高估了可能的解，譬如解是6的话你不能估成7，这样的估价函数是不行的。下面给的h函数是一定估小的，虽然我觉得可能优化的不是特别的大。
细节等别的地方后面再慢慢学习，先照着别人的拍一题加深一下认识。。
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define maxnode 4000
#define maxn 80
#define eps 1e-8
int L[maxnode], R[maxnode], U[maxnode], D[maxnode];
int col[maxnode];
int S[maxn], H[maxn];
int size;
int n, m, K;
int ak; // currently best dep
void link(int r, int c)
{
S[c]++; col[size] = c;
U[size] = U[c]; D[U[c]] = size;
D[size] = c; U[c] = size;
if (H[r] == -1) H[r] = L[size] = R[size] = size;
else{
L[size] = L[H[r]]; R[L[H[r]]] = size;
R[size] = H[r]; L[H[r]] = size;
}
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;
}
}
// evaluating function
int hfunc()
{
bool vis[maxn];
memset(vis, 0, sizeof(vis));
int cnt = 0;
for (int i = R[0]; i; i = R[i]){
if (vis[i]) continue;
cnt++; vis[i] = true;
for (int j = D[i]; j != i; j = D[j]){
for (int k = R[j]; k != j; k = R[k]){
vis[col[k]] = true;
}
}
}
return cnt;
}
void dance(int dep)
{
int ans = hfunc();
if (ans + dep > K || ans + dep >= ak) return;
if (R[0] == 0){
if (dep < ak) ak = dep; return;
}
int minv = maxn; int c;
for (int i = R[0]; i; i = R[i]){
if (S[i] < minv) minv = S[i], 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);
}
dance(dep + 1);
for (int j = L[i]; j != i; j = L[j]){
resume(j);
}
resume(i);
}
return;
}
double x[100], y[100];
double xx[100], yy[100];
int dcmp(double x){
return (x > eps) - (x < -eps);
}
double dist(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
int main()
{
int T; cin >> T;
while (T--)
{
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= n; i++){
scanf("%lf%lf", &x[i], &y[i]);
}
for (int i = 1; i <= m; i++){
scanf("%lf%lf", &xx[i], &yy[i]);
}
double l = 0, r = 1500;
while (dcmp(r - l) > 0){
for (int i = 0; i <= n; i++){
S[i] = 0; U[i] = D[i] = i;
L[i + 1] = i; R[i] = i + 1;
}
R[n] = 0;
memset(H, -1, sizeof(H)); size = n + 1;
double mid = (l + r) / 2;
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
if (mid>=dist(xx[i], yy[i], x[j], y[j])){
link(i, j);
}
}
}
ak = maxn;
dance(0);
if (ak <= K) r = mid;
else l = mid;
}
printf("%.6lf
", l);
}
return 0;
}