题目大意:

有一堆雷达工作站,安放至多k个人在这些工作站中,找到一个最小的雷达监控半径可以使k个工作人所在的雷达工作站覆盖所有城市

二分半径的答案,每次利用dlx的重复覆盖来判断这个答案是否正确

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
#include <cmath> using namespace std;
#define N 55
#define MAXNODE 3000
const double INF = 1e9;
const double eps = 1e-; int n,m,k; struct DLX{
int n,m,size;
int U[MAXNODE] , D[MAXNODE] , L[MAXNODE] , R[MAXNODE];
int col[MAXNODE] , row[MAXNODE];
int first[N] , cnt_col[N];
bool v[MAXNODE]; void init(int _n , int _m)
{
n = _n , m = _m , size = _m;
for(int i= ; i<=m ; i++){
U[i] = D[i] = i;
L[i] = i- , R[i] = i+;
col[i] = i , row[i] = ;
}
L[] = m , R[m] = ;
for(int i= ; i<=n ; i++) first[i] = -;
for(int i= ; i<=m ; i++) cnt_col[i] = ;
} void link(int r , int c)
{
++size;
U[D[c]] = size , D[size] = D[c];
U[size] = c , D[c] = size;
cnt_col[c]++; if(first[r]<) first[r] = L[size] = R[size] = size;
else{
R[size] = R[first[r]] , L[R[first[r]]] = size;
L[size] = first[r] , R[first[r]] = size;
}
row[size] = r , col[size] = c;
} 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;
}
} int f()
{
int ret = ;
for(int c=R[] ; c!= ; c=R[c]) v[c]=true;
for(int c=R[] ; c!= ; 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)
{
//这里k表示题目所给意思让我们至多在dlx中选择k行
if(d+f() > k) return false;
if(!R[]) return d<=k;
int st = R[];
for(int i=R[] ; i!= ; i=R[i])
if(cnt_col[st]>cnt_col[i]) st=i; for(int i=D[st] ; i!=st ; i=D[i]){
Remove(i);
for(int j=R[i] ; j!=i ; j=R[j]) Remove(j);
if(Dance(d+)) return true;
for(int j=L[i] ; j!=i ; j=L[j]) Resume(j);
Resume(i);
}
return false;
}
}dlx; struct Point{
double x,y;
}p1[N] , p2[N]; double getDis(int i , int j)
{
return sqrt((p1[i].x-p2[j].x)*(p1[i].x-p2[j].x)+(p1[i].y-p2[j].y)*(p1[i].y-p2[j].y));
} bool check(double mid)
{
dlx.init(m , n);
for(int i= ; i<=m ; i++){
for(int j=; j<=n ;j++){
if(getDis(j , i)<=mid) dlx.link(i,j);
}
}
return dlx.Dance();
} double bin_search()
{
double l= , r=INF;
while(r-l>eps){
double mid = (l+r)/;
if(check(mid)) r=mid;
else l=mid;
}
return r;
} int main()
{
// freopen("a.in" , "r" , stdin);
int T;
scanf("%d" , &T);
while(T--)
{
scanf("%d%d%d" , &n , &m , &k);
for(int i= ; i<=n ; i++)
scanf("%lf%lf" , &p1[i].x , &p1[i].y);
for(int i= ; i<=m ; i++)
scanf("%lf%lf" , &p2[i].x , &p2[i].y);
printf("%.6lf\n" , bin_search());
}
return ;
}

最新文章

  1. viewDidLoad &amp;&amp; loadView
  2. #ifdef __cplusplus extern &quot;C&quot;
  3. B/S 和 C/S
  4. 201521123001《Java程序设计》第12周学习总结
  5. 解决maven项目Cannot change version of project facet Dynamic web module to 3.0
  6. [Swift]LeetCode343. 整数拆分 | Integer Break
  7. orleans exception序列化
  8. TensorFlow学习入门
  9. axios post参数为空
  10. Mysql中count(*)和limit同时使用的问题
  11. win8 应用商店程序使用SQLITE数据库
  12. 嵌入式开发值zynq---zynq中tlv320aic23b spi的驱动移植
  13. Locust性能测试1-环境准备与基本使用
  14. 【CTF WEB】GCTF-2017读文件
  15. unity forward renderer的 base pass rt设置
  16. Extjs学习笔记--(六,选择器)
  17. mysql参数安全设置
  18. MySQL GTID (四)
  19. Java常见错误及解决方案
  20. 【BZOJ】1009: [HNOI2008]GT考试(dp+矩阵乘法+kmp+神题)

热门文章

  1. Altium Designer的一些功能
  2. solr 常见异常
  3. Setting up IPS/inline for Linux in Suricata
  4. 动手实现 Redux(六):Redux 总结
  5. state vs props
  6. PKU_campus_2018_H Safe Upper Bound
  7. OCP 11g 第二章练习
  8. promise 里面的 console.info 打印信息 并不准确,后期有修改对象数据,会覆盖,影响之前的显示
  9. 下拉列表事件 Dropdown iview
  10. vscode 快捷键 ctrl+shift+F 冲突了 解决办法