这是带门槛的最小生成树：只有距离平方不小于 c 的边允许使用，直接在完全图上做 Prim，若中途出现不可达点则答案不存在。
OJ: luogu
题目 ID: P2212
难度:普及+/提高
标签:图论最小生成树贪心
日期: 2026-06-20 01:03
题意
给出 n 个点的坐标。
两点之间连边的代价定义为距离平方：
(x_i-x_j)^2 + (y_i-y_j)^2
但题目规定：如果这条边的代价小于 c，那么这条边根本不能用。
问在只允许使用代价不小于 c 的边时，能否把所有点连通；如果能，最小总代价是多少；如果不能，输出 -1。
思路
先看一个只适合小数据的暴力：
cpp
// brute.cpp：小图枚举所有允许边的生成树。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 50;
const int INF = 1e9;
struct Edge {
int u, v, w;
} edges[MAXM];
int n, limit_c;
int x[MAXN], y[MAXN];
int edge_cnt;
int picked[MAXM];
int fa[MAXN];
int best_answer = INF;
int dis2(int i, int j) {
int dx = x[i] - x[j];
int dy = y[i] - y[j];
return dx * dx + dy * dy;
}
void init_dsu() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find_root(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_root(fa[x]);
return fa[x];
}
bool unite(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x == y) {
return false;
}
fa[x] = y;
return true;
}
void check_tree(int picked_cnt) {
if (picked_cnt != n - 1) {
return;
}
init_dsu();
int sum = 0;
for (int i = 1; i <= picked_cnt; i++) {
Edge &e = edges[picked[i]];
if (!unite(e.u, e.v)) {
return;
}
sum += e.w;
}
int root = find_root(1);
for (int i = 2; i <= n; i++) {
if (find_root(i) != root) {
return;
}
}
best_answer = min(best_answer, sum);
}
void dfs(int pos, int picked_cnt) {
if (picked_cnt > n - 1) {
return;
}
if (pos > edge_cnt) {
check_tree(picked_cnt);
return;
}
picked[picked_cnt + 1] = pos;
dfs(pos + 1, picked_cnt + 1);
dfs(pos + 1, picked_cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> limit_c;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
edge_cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int w = dis2(i, j);
if (w < limit_c) {
continue;
}
edges[++edge_cnt] = {i, j, w};
}
}
dfs(1, 0);
if (best_answer == INF) {
cout << -1 << '\n';
} else {
cout << best_answer << '\n';
}
return 0;
}暴力直接把所有“允许使用”的边列出来，然后枚举哪些边能组成生成树，取总代价最小的那个。
这个思路按定义完全正确，但边数一大就不能枚举了。
这题本质上仍然是最小生成树，只不过有一条额外限制：
- 边权
< c的边不能选
也就是说，我们是在一张“删掉非法边后的图”上求 MST。
由于原图本来是完全图，而 n <= 2000，不显式存下全部边会更省事，所以直接用 Prim O(n^2)：
- 初始任选一个点加入生成树
dist_to_tree[i]维护点i到当前生成树的最小合法边权- 每次选一个
dist_to_tree最小的未访问点加入答案 - 再用这个点去更新其它点的最优接入代价
如果某一轮最小的 dist_to_tree 仍然是无穷大，说明剩下点都无法通过合法边接到当前生成树上，答案就是 -1。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int INF = 1e9;
int n, limit_c;
int x[MAXN], y[MAXN];
int dist_to_tree[MAXN];
bool vis[MAXN];
int dis2(int i, int j) {
int dx = x[i] - x[j];
int dy = y[i] - y[j];
return dx * dx + dy * dy;
}
int prim() {
for (int i = 1; i <= n; i++) {
dist_to_tree[i] = INF;
vis[i] = false;
}
dist_to_tree[1] = 0;
int answer = 0;
for (int i = 1; i <= n; i++) {
int u = 0;
for (int j = 1; j <= n; j++) {
if (vis[j]) {
continue;
}
if (u == 0 || dist_to_tree[j] < dist_to_tree[u]) {
u = j;
}
}
if (u == 0 || dist_to_tree[u] == INF) {
return -1;
}
vis[u] = true;
answer += dist_to_tree[u];
for (int v = 1; v <= n; v++) {
if (vis[v]) {
continue;
}
int w = dis2(u, v);
if (w < limit_c) {
continue;
}
if (w < dist_to_tree[v]) {
dist_to_tree[v] = w;
}
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> limit_c;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
cout << prim() << '\n';
return 0;
}复杂度
设点数为 n。
Prim 每轮：
- 找一个最便宜接入的新点
- 再扫一遍所有点更新距离
所以：
- 时间复杂度
- 空间复杂度
总结
这题难点不在“距离平方”这个细节，而在先看出它仍然是 MST：只不过把边权小于 c 的边全部禁用了。识别成“带门槛的最小生成树”后，Prim 就能直接处理。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
