把已有道路先用并查集合并，再在所有点对构成的完全图上跑 Kruskal 求最小新增长度。
OJ: luogu
题目 ID: P2872
难度:普及/提高-
标签:最小生成树Kruskal并查集几何
日期: 2026-01-03 09:56
题意
给定 n 个点的坐标，以及 m 条已经建好的道路。
现在可以在任意两个点之间新建道路，费用为两点之间的欧氏距离。要求新增一些道路，使所有点连通，并让新增道路总长度最小。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：Prim 版本最小生成树，用不同实现辅助对拍。
const int MAXN = 105;
const double INF = 1e100;
int n, m;
long long x_pos[MAXN], y_pos[MAXN];
double cost[MAXN][MAXN];
double dist_to_tree[MAXN];
bool used[MAXN];
double distance_between(int i, int j) {
double dx = (double)(x_pos[i] - x_pos[j]);
double dy = (double)(y_pos[i] - y_pos[j]);
return sqrt(dx * dx + dy * dy);
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x_pos[i] >> y_pos[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = distance_between(i, j);
}
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
cost[u][v] = 0.0;
cost[v][u] = 0.0;
}
}
double prim() {
for (int i = 1; i <= n; i++) {
dist_to_tree[i] = INF;
used[i] = false;
}
dist_to_tree[1] = 0.0;
double answer = 0.0;
for (int step = 1; step <= n; step++) {
int u = 0;
for (int i = 1; i <= n; i++) {
if (!used[i] && (u == 0 || dist_to_tree[i] < dist_to_tree[u])) {
u = i;
}
}
used[u] = true;
answer += dist_to_tree[u];
for (int v = 1; v <= n; v++) {
if (!used[v] && cost[u][v] < dist_to_tree[v]) {
dist_to_tree[v] = cost[u][v];
}
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
cout << fixed << setprecision(2) << prim() << '\n';
return 0;
}这道题是最小生成树模型。区别在于有些道路已经存在，不需要再花钱。
可以把已有道路看作费用为 0 的边。实现时不必把它们加入边数组排序，直接在一开始用并查集合并它们的两个端点即可。
然后枚举所有点对，计算欧氏距离，得到一张完全图。因为 n <= 1000，完全图大约有 5 * 10^5 条边，可以接受。
最终做 Kruskal：
- 已有道路先合并；
- 所有候选新道路按长度排序；
- 如果当前边连接了两个不同连通块，就选它并累加长度；
- 全部连通后得到最小新增长度。
brute.cpp 用 Prim 在完整费用矩阵上求 MST，和正解的 Kruskal 实现不同，用于小数据验证。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXE = 1000005;
struct Edge {
int u, v;
double w;
};
int n, m;
long long x_pos[MAXN], y_pos[MAXN];
Edge edge[MAXE];
int edge_count;
int father[MAXN];
bool cmp_edge(const Edge &a, const Edge &b) {
return a.w < b.w;
}
int find_root(int x) {
if (father[x] == x) {
return x;
}
father[x] = find_root(father[x]);
return father[x];
}
bool merge_set(int x, int y) {
int rx = find_root(x);
int ry = find_root(y);
if (rx == ry) {
return false;
}
father[rx] = ry;
return true;
}
double distance_between(int i, int j) {
double dx = (double)(x_pos[i] - x_pos[j]);
double dy = (double)(y_pos[i] - y_pos[j]);
return sqrt(dx * dx + dy * dy);
}
void add_edge(int u, int v, double w) {
edge_count++;
edge[edge_count].u = u;
edge[edge_count].v = v;
edge[edge_count].w = w;
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x_pos[i] >> y_pos[i];
father[i] = i;
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
merge_set(u, v); // 已经存在的路不需要再付费。
}
}
void build_all_edges() {
edge_count = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
add_edge(i, j, distance_between(i, j));
}
}
}
void solve() {
build_all_edges();
sort(edge + 1, edge + edge_count + 1, cmp_edge);
double answer = 0.0;
for (int i = 1; i <= edge_count; i++) {
if (merge_set(edge[i].u, edge[i].v)) {
answer += edge[i].w;
}
}
cout << fixed << setprecision(2) << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
完全图边数为
空间复杂度为
总结
“已有边 + 最小新增代价连通”可以直接转成 MST。
已有道路先合并，相当于已经免费选入；剩下的工作就是在所有可能新道路中按 Kruskal 选择最短的连接边。