题意：
N个城市，M个雷达站，K个操作员，问雷达的半径至少为多大，才能覆盖所有城市。M个雷达中最多只能有K个同时工作。
思路：
二分雷达的半径，看每个雷达可以覆盖哪些城市，然后做重复覆盖，判断这个半径是否可行。
我是直接二分的半径，跑了300+ms，看了Virtual Judge上面跑得快的代码，才发现为了不浪费半径的长度，最小的半径一定等于某一个雷达站到某一个城市之间的距离。这样一来枚举量就小了很多，只需要15ms……
代码：
300+ms的 -_-
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <cctype> 15 #include <time.h> 16 17 using namespace std; 18 19 const double eps = 1e-8; 20 const int INF = 1<<30; 21 const int MAXN = 55; 22 const int MAXR = 55; 23 const int MAXNODE = MAXN*MAXR; 24 25 struct DLX { 26 // 行编号从1开始，列编号为1~n，结点0是表头结点；结点1~n是各列顶部的虚拟结点 27 int n, sz; // 列数，结点总数 28 int S[MAXN]; //各列结点数 29 30 int row[MAXNODE], col[MAXNODE]; //各结点行列编号 31 int L[MAXNODE], R[MAXNODE], U[MAXNODE], D[MAXNODE]; //十字链表 32 33 int ansd, ans[MAXR]; // 解 34 35 void init(int n) { //n是列数 36 this->n = n; 37 38 //虚拟结点 39 for (int i = 0; i <= n; i++) { 40 U[i] = i; D[i] = i; L[i] = i-1; R[i] = i+1; 41 } 42 R[n] = 0; L[0] = n; 43 sz = n+1; 44 memset(S, 0, sizeof(S)); 45 } 46 47 void addRow(int r, vector<int> columns) { 48 //这一行的第一个结点 49 //行没有设头结点，每一行连成一个环形 50 int first = sz; 51 for (int i = 0; i < columns.size(); i++) { 52 int c = columns[i]; 53 L[sz] = sz-1; R[sz] = sz+1; D[sz] = c; U[sz] = U[c]; 54 D[U[c]] = sz; U[c] = sz; 55 row[sz] = r; col[sz] = c; 56 S[c]++; sz++; 57 } 58 R[sz-1] = first; L[first] = sz-1; 59 } 60 61 //顺着链表A，遍历s外的其他元素 62 #define FOR(i, A, s) for (int i = A[s]; i != s; i = A[i]) 63 64 void remove(int c) { //删除c列 65 FOR(i, D, c) { 66 L[R[i]] = L[i]; R[L[i]] = R[i]; 67 } 68 } 69 70 void restore(int c) { //回连c列 71 FOR(i, U, c) { 72 L[R[i]] = R[L[i]] = i; 73 } 74 } 75 76 bool vis[MAXN]; 77 78 int f() { 79 int ret = 0; 80 FOR(c, R, 0) vis[c] = true; 81 FOR(c, R, 0) if (vis[c]) { 82 ret++; vis[c] = false; 83 FOR(i, D, c) FOR(j, R, i) 84 vis[col[j]] = false; 85 } 86 return ret; 87 } 88 89 void dfs(int d) { //d为递归深度 90 if (d+f()>=ansd) return ; 91 if (R[0] == 0) { //找到解 92 ansd = min(ansd, d); //记录解的长度 93 return ; 94 } 95 96 //找S最小的C列 97 int c = R[0]; //第一个未删除的列 98 for (int i = R[0]; i != 0; i = R[i]) if (S[i]<S[c]) c = i; 99 100 for (int i = D[c]; i != c; i = D[i]) { //用结点i所在的行覆盖第c列 101 remove(i); 102 for (int j = R[i]; j != i; j = R[j]) remove(j); //删除节结点i所在行覆盖第c列 103 ans[d] = row[i]; 104 dfs(d+1); 105 for (int j = L[i]; j != i; j = L[j]) restore(j); // 恢复 106 restore(i); 107 } 108 } 109 110 int solve() { 111 ansd = INF; 112 dfs(0); 113 return ansd; 114 } 115 }; 116 117 DLX solver; 118 vector<int> columns; 119 120 int n, m, k; 121 double a[MAXN][2]; 122 double b[MAXN][2]; 123 double G[MAXN][MAXN]; 124 125 int check(double x) { 126 solver.init(n); 127 for (int i = 0; i < m; i++) { 128 columns.clear(); 129 for (int j = 0; j < n; j++) if (G[i][j]<=x) 130 columns.push_back(j+1); 131 if (!columns.empty()) solver.addRow(i+1, columns); 132 } 133 return solver.solve(); 134 } 135 136 int main() { 137 #ifdef Phantom01 138 freopen("HDU2295.txt", "r", stdin); 139 #endif //Phantom01 140 141 int T; 142 scanf("%d", &T); 143 while (T--) { 144 scanf("%d%d%d", &n, &m, &k); 145 for (int i = 0; i < n; i++) 146 scanf("%lf%lf", &a[i][0], &a[i][1]); 147 for (int i = 0; i < m; i++) 148 scanf("%lf%lf", &b[i][0], &b[i][1]); 149 double l = 0, r = 0, mm; 150 for (int i = 0; i < m; i++) { 151 for (int j = 0; j < n; j++) { 152 G[i][j] = sqrt((b[i][0]-a[j][0])*(b[i][0]-a[j][0]) + (b[i][1]-a[j][1])*(b[i][1]-a[j][1])); 153 r = max(r, G[i][j]); 154 } 155 } 156 while (abs(r-l)>eps) { 157 mm = (l+r)/2; 158 if (check(mm)>k) l = mm; 159 else r = mm; 160 } 161 printf("%.6f ", r+eps); 162 } 163 164 return 0; 165 }