2分答案+DLX判断可行
不使用的估计函数的可重复覆盖的搜索树将十分庞大
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <vector> using namespace std; #define FOR(i,A,s) for(int i = A[s]; i != s; i = A[i]) #define exp 1e-8 const int MAX = 111111, MAXR = 1111, MAXC = 1111; int n, m, k, t; struct DLX { int n, Size;//Size为尾指针，真正大小 int row[MAX], col[MAX];//记录每个点的行列 int U[MAX], D[MAX], R[MAX], L[MAX]; //4个链表 int S[MAXC];//每列1的个数 int ncnt, ans[MAXR]; void init (int n) { this->n = n; //增加n+1个辅助链表，从0到n for (int i = 0; i <= n; i++) U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1; R[n] = 0, L[0] = n; //头尾相接 Size = n + 1; memset (S, 0, sizeof S); } //逐行添加 void addRow (int r, int columns[111]) { int first = Size; for (int i = 1; i <= n ; i++) { if (columns[i] == 0) continue; int c = i; L[Size] = Size - 1, R[Size] = Size + 1; U[Size] = U[c], D[Size] = c;//插入第c列 D[U[c]] = Size, U[c] = Size; //注意顺序!!! row[Size] = r, col[Size] = c; Size++, S[c]++; } if (Size > first) R[Size - 1] = first, L[first] = Size - 1; //头尾相接 } void Remove (int c) { //精确覆盖 // L[R[c]] = L[c], R[L[c]] = R[c]; // FOR (i, D, c) // FOR (j, R, i) // U[D[j]] = U[j], D[U[j]] = D[j], --S[col[j]]; //重复覆盖 for (int i = D[c]; i != c; i = D[i]) L[R[i]] = L[i], R[L[i]] = R[i]; } void Restore (int c) { // FOR (i, U, c) // FOR (j, L, i) // ++S[col[j]], U[D[j]] = j, D[U[j]] = j; // L[R[c]] = c, R[L[c]] = c; //重复覆盖 for (int i = U[c]; i != c; i = U[i]) L[R[i]] = R[L[i]] = i; } bool v[MAX]; int ff() { int ret = 0; for (int c = R[0]; c != 0; c = R[c]) v[c] = true; for (int c = R[0]; c != 0; 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 dfs (int d) { if (d + ff() > k) return 0; if (R[0] == 0) { ncnt = d; return d <= k; } int c = R[0]; for (int i = R[0]; i != 0; i = R[i]) if (S[i] < S[c]) c = i; //Remove (c);//精确覆盖 FOR (i, D, c) { Remove (i);//重复覆盖 ans[d] = row[i]; //FOR (j, R, i) Remove (col[j]); FOR (j, R, i) Remove (j); if (dfs (d + 1) ) return 1; //FOR (j, L, i) Restore (col[j]); FOR (j, L, i) Restore (j); Restore (i);//重复覆盖 } //Restore (c);//精确覆盖 return 0; } bool solve (vector<int> &v) { v.clear(); if (!dfs (0) ) return 0; for (int i = 0; i < ncnt; i++) v.push_back (ans[i]); return 1; } } f; struct node { int x, y; } g[100], Ra[100]; int columns[111][111]; double dis[111][111]; inline double getdis (node a, node b) { return sqrt (double ( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) ) ); } bool make (double mid) { f.init (n); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) columns[i][j] = dis[i][j] <= mid; for (int i = 1; i <= m; i++) f.addRow (i, columns[i]); return f.dfs (0); } int main() { scanf ("%d", &t); while (t--) { scanf ("%d %d %d", &n, &m, &k); for (int i = 1; i <= n; i++) scanf ("%d %d", &g[i].x, &g[i].y); for (int i = 1; i <= m; i++) scanf ("%d %d", &Ra[i].x, &Ra[i].y); double l = 1e9, r = 0; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { dis[i][j] = getdis (Ra[i], g[j]); l = min (dis[i][j], l), r = max (r, dis[i][j]); } double ans = -1; while (r - l > 1e-7) { double mid = (r + l) / 2.; if (make (mid) ) { ans = mid; r = mid - exp; } else l = mid + exp; } printf ("%.6f ", ans); } return 0; }