P2872

[USACO07DEC] Building Roads S

题目描述

给定 $n$ 个点的坐标，第 $i$ 个点的坐标为 $(x_i,y_i)$ ，这 $n$ 个点编号为 $1$ 到 $n$ 。给定 $m$ 条边，第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

第一行两个整数 $n,m$ 代表点数与边数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 代表第 $i$ 个点的坐标。
接下来 $m$ 行每行两个整数 $u_i,v_i$ 代表第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。

输出格式

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差，请用 $64$ 位实型变量进行计算。

输入输出样例

输入样例 #1

输出样例 #1

4.00

说明/提示

数据规模与约定

对于 $100\%$ 的整数， $1 \le n,m \le 1000$ ， $1 \le x_i,y_i \le 10^6$ ， $1 \le u_i,v_i \le n$ 。

说明

Translated by 一只书虫仔。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P2872 [USACO07DEC] Building Roads S 题解 Author: Yuyi 题意分析本题给定 $N$ 个点的坐标，并且告知图里已经提前建好了 $M$ 条边。题目要求我们在此基础上额外再连一些边，让所有的 $N$ 个点连通，并且要求额外添加的边权（距离）总和最小。这依然是一道标准的 Kruskal 最小生成树，唯一的区别在…

点击展开完整题解点击收起题解

2026年8月9日 22:34

P2872 [USACO07DEC] Building Roads S 题解

Author: Yuyi

题意分析

本题给定 $N$ 个点的坐标，并且告知图里已经提前建好了 $M$ 条边。题目要求我们在此基础上额外再连一些边，让所有的 $N$ 个点连通，并且要求额外添加的边权（距离）总和最小。这依然是一道标准的 Kruskal 最小生成树，唯一的区别在于“提前修建的边”。对于已经提前修建好的边，我们可以认为它们的“修建成本”为 $0$ ，或者更直观一点，直接在跑 Kruskal 之前，把这 $M$ 条边涉及的点在并查集里提前合并！这样后续跑正常 Kruskal 的时候，原先就连通的区块就不会再花冤枉钱去铺路，而必须铺路的地方自然也会贪心地选出最短的路径。

正解推导过程

并查集初始化与预合并：读取完坐标后，我们将并查集初始化。紧接着读取那 $M$ 条已经存在的边，每读入一条，就直接进行 find 并合并，同时用 cnt 记录一下成功合并的次数（即有效连通的边数）。
构建完全图：枚举所有的点对 $(i, j)$ ，计算两点之间的欧几里得直线距离（题目要求用 64 位实型，即 double）存入数组中。点数为 1000，边数约为 50 万条。
Kruskal 连边：按距离从小到大对所有边进行排序。接着遍历这些边，如果两端点不在同一个连通块里，就花费当前的距离将它们合并，累加距离到 ans 里，且 cnt++。
结束判定：不管是在初始预合并阶段，还是后续 Kruskal 阶段，只要总有效连通数 cnt 达到了 $N-1$ ，说明整个图已经完全连通，此时直接 break 退出循环，输出 ans 即可。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 500005; // 按照最大边数 N(N-1)/2 约 50万统一调配
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m;
int x[maxn],y[maxn];
struct Edge
{
    int u,v;
    double w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void solve()
{
    read(n),read(m);
    rep(i,1,n) read(x[i]),read(y[i]);
    rep(i,1,n) fa[i] = i;
    int cnt = 0;
    rep(i,1,m)
    {
        int u,v;
        read(u),read(v);
        int fu = find(u);
        int fv = find(v);
        if(fu != fv)
        {
            fa[fu] = fv;
            cnt++;
        }
    }
    int tot = 0;
    rep(i,1,n)
    {
        rep(j,i+1,n)
        {
            tot++;
            e[tot].u = i;
            e[tot].v = j;
            e[tot].w = sqrt((double)(x[i]-x[j])*(x[i]-x[j]) + (double)(y[i]-y[j])*(y[i]-y[j]));
        }
    }
    sort(e+1,e+1+tot,cmp);
    double ans = 0;
    rep(i,1,tot)
    {
        if(cnt == n-1) break;
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
    }
    cout << fixed << setprecision(2) << ans << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：预处理 $M$ 条边耗时 $O(M)$ 。然后计算所有点对距离需 $O(N^2)$ 。生成的边数约为 $\frac{N^2}{2} \approx 5 \times 10^5$ ，排序耗时 $O(N^2 \log N)$ 。最后 Kruskal 合并由于并查集近乎 $O(1)$ ，耗时也是 $O(N^2)$ 。综合时间复杂度为 $O(N^2 \log N)$ ，在 $N \le 1000$ 时大约只有 $10^7$ 次计算，轻松过掉。
空间复杂度：由于最占空间的是存放全图边的 Edge 数组，最大接近 50 万条边。我严格遵照习惯，将所有主要数组（x, y, fa, e）直接用常数 maxn = 500005 齐平开辟，空间耗费约 10MB 左右，绝对符合题目的内存限制。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。