最小点覆盖模板题。
思路
考虑二分直径 \(x\)。
我们将距离 \(>x\) 的点对连一条边，那么每一条边的两端至少有一端需要被删掉。
这是最小点覆盖的定义。
那么就是判断最小点覆盖是否小于等于 \(k\)。
发现这个问题并不好用一些多项式复杂度的做法解决。
考虑暴搜。
每一次我们把度数最大的点拿出来。
我们此时有两种情况。
- 选择这个点，继续搜索。
- 选择这个点的所有邻居，继续搜索。
此时的复杂度为：
\[T(k)=T(k-1)+T(k-du)+O(n) \]\(du\) 就是此时最大的度数。
发现当最大的度数为一时，这个做法最坏可以达到 \(O(2^kn)\)。
但是考虑当最大的度数小于等于二时。
整张图是一堆链和一堆环的组合。
这种图的最小点覆盖是极其好计算的。
所以对于最大的度数小于等于二时，我们可以特殊处理，不需要搜索。
那么此时复杂度就变成了：
\[T(k)=T(k-1)+T(k-3)+O(n) \]搜索次数在 \(k=30\) 时最多只有四万，并且很难卡满，可以轻松通过。
Code
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1010];
int b[1010];
int du[1010];
int vs[1010];
vector<int> rs;
vector<int> qs;
vector<int> to[1010];
inline void get(int x) {
deque<int> q;
vs[x] = 1, q.push_back(x);
auto sol1 = [&](int x, auto sol1) -> void {
vs[x] = 1, q.push_front(x);
for (auto i : to[x]) if (!vs[i] && du[i]) sol1(i, sol1);
};
auto sol2 = [&](int x, auto sol2) -> void {
vs[x] = 1, q.push_back(x);
for (auto i : to[x]) if (!vs[i] && du[i]) sol2(i, sol2);
};
int o = 0;
for (auto i : to[x])
if (!vs[i] && du[i]) {
if (o == 1) sol2(i, sol2), o = 2;
if (o == 0) sol1(i, sol1), o = 1;
}
int ct = 0;
for (auto i : q) if (du[i] == 1) ct++;
while (q.size() >= 2) {
q.pop_front();
rs.push_back(q.front());
q.pop_front();
}
if (ct == 0 && q.size()) rs.push_back(q.front());
}
inline void add(int p) { for (auto i : to[p]) du[i]--; vs[p] = 1, rs.push_back(p); }
inline void del(int p) { for (auto i : to[p]) du[i]++; vs[p] = 0, rs.pop_back(); }
inline bool dfs() {
if (rs.size() <= k) {
int p = 0;
for (int i = 1; i <= n; i++) if (!vs[i] && du[i] > du[p]) p = i;
if (du[p] == 0) {
return 1;
} else if (du[p] > 2) {
vector<int> r;
for (auto i : to[p]) if (!vs[i]) r.push_back(i);
for (auto i : r) add(i); if (dfs()) return 1;
for (auto i : r) del(i);
add(p); if (dfs()) return 1;
del(p);
} else {
vector<int> r, l = rs;
for (int i = 1; i <= n; i++) if (!vs[i] && du[i]) r.push_back(i);
for (int i = 1; i <= n; i++) if (!vs[i] && du[i]) get(i);
if (rs.size() <= k) return 1;
for (auto i : r) vs[i] = 0;
rs = l;
}
}
return 0;
}
inline bool chk(int x) {
for (int i = 1; i <= n; i++) to[i].clear(), du[i] = vs[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if ((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]) > x) {
to[i].push_back(j), du[i]++;
to[j].push_back(i), du[j]++;
}
return rs.clear(), dfs();
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
long long l = 0, r = 2e9;
while (l <= r) {
long long mid = (l + r) >> 1;
if (chk(mid)) {
r = mid - 1, qs = rs;
} else {
l = mid + 1;
}
}
memset(vs, 0, sizeof vs);
for (auto i : qs) vs[i] = 1;
for (int i = 1; i <= n && k; i++) if (vs[i] == 1) cout << i << " ", k--;
for (int i = 1; i <= n && k; i++) if (vs[i] == 0) cout << i << " ", k--;
}