公路修建

GitHub跳转原题关系图返回列表

题面按轮修路的过程本质是在构造欧几里得最小生成树，最终总长度就等于 MST 边长之和；点数较大时直接用 Prim 求解即可。

OJ: luogu

题目 ID: P1265

难度:普及+/提高

标签:图论最小生成树贪心

日期: 2026-06-20 01:06

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给出 nn 个城市的平面坐标。

题面描述了一个按轮修路的过程：

  • 每个城市或城市联盟，都去找距离自己最近的另一个城市或联盟申请修路
  • 如果申请边形成环，就否掉其中最短的一条
  • 不断重复，直到所有城市都合成一个联盟

问最终修建的公路总长度是多少，结果保留两位小数。

思路

先看一个只适合很小数据的暴力：

cpp
// brute.cpp：小图枚举所有生成树，直接比较总长度。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 30;
const long double INF = 1e100;

struct Edge {
    int u, v;
    long long d2;
} edges[MAXM];

int n;
long long x[MAXN], y[MAXN];
int edge_cnt;
int picked[MAXM];
int fa[MAXN];
long double best_answer = INF;

long long dis2(int i, int j) {
    long long dx = x[i] - x[j];
    long long 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();
    long double sum = 0;

    for (int i = 1; i <= picked_cnt; i++) {
        Edge &e = edges[picked[i]];
        if (!unite(e.u, e.v)) {
            return;
        }
        sum += sqrtl((long double)e.d2);
    }

    int root = find_root(1);
    for (int i = 2; i <= n; i++) {
        if (find_root(i) != root) {
            return;
        }
    }

    if (sum < best_answer) {
        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;
    }

    if (picked_cnt + (edge_cnt - pos + 1) < n - 1) {
        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;
    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++) {
            edges[++edge_cnt] = {i, j, dis2(i, j)};
        }
    }

    dfs(1, 0);

    cout << fixed << setprecision(2) << (double)best_answer << '\n';

    return 0;
}

暴力直接枚举所有生成树，计算总长度，取最小值。

这个做法很好理解，但显然不可能用于 n=5000n = 5000。

这题真正的关键，是看出题面这个“按轮找最近点、合并联盟”的过程，本质上是在做一种 Boruvka 风格的最小生成树构造。

为什么可以这样理解？

在任意一轮里，每个连通块都尝试选一条“连向外部的最短边”。 根据最小生成树的切分性质，这样的边一定可以安全加入某棵 MST。

题面里关于：

  • 多个城市申请同一条边时合并
  • 成环时删掉最短边

本质上都只是为了保证：

  • 不会重复加边
  • 不会真的把环整条留进结果里

所以，不管题面过程怎么描述，最终留下来的总长度，其实就等于这批点的欧几里得最小生成树长度。

既然只要求总长度，直接做 MST 就够了。

由于图是完全图，边数是 O(n2)O(n^2)，而 n=5000n = 5000，不必显式存下所有边，直接用 PrimO(n2)Prim O(n^2) 最合适：

  1. 任取一个点作为起点
  2. disttotree[i]dist_to_tree[i] 维护点 ii 到当前生成树的最小距离平方
  3. 每次选一个最近的未访问点加入生成树
  4. 再用它更新其它点的最优接入距离

实现时有个小优化：

  • 比较大小时，全程用距离平方
  • 只有真正把一条边加入答案时，才对这条边开方累加

因为平方根是单调的，这样不会影响 MST 的选边顺序。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const long long INF = (1LL << 62);

int n;
long long x[MAXN], y[MAXN];
long long dist_to_tree[MAXN];
bool vis[MAXN];

long long dis2(int i, int j) {
    long long dx = x[i] - x[j];
    long long dy = y[i] - y[j];
    return dx * dx + dy * dy;
}

long double prim() {
    for (int i = 1; i <= n; i++) {
        dist_to_tree[i] = INF;
        vis[i] = false;
    }

    dist_to_tree[1] = 0;
    long double 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;
            }
        }

        vis[u] = true;
        answer += sqrtl((long double)dist_to_tree[u]);

        for (int v = 1; v <= n; v++) {
            if (vis[v]) {
                continue;
            }
            long long w = dis2(u, v);
            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;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    cout << fixed << setprecision(2) << (double)prim() << '\n';

    return 0;
}

复杂度

设点数为 nn。

Prim 每轮：

  • 选一个最近的未访问点
  • 再扫一遍所有点更新距离

所以：

  • 时间复杂度 O(n2)O(n^2)
  • 空间复杂度 O(n)O(n)

总结

这题最容易被题面过程绕进去。真正要抓住的是：它虽然写成了“多轮审批修路”，但最终本质还是欧几里得最小生成树。识别出这一点之后，问题就会立刻变成一道很标准的 Prim。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析