P3366

【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ 。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

数据规模：

对于 $20\%$ 的数据， $N\le 5$ ， $M\le 20$ 。

对于 $40\%$ 的数据， $N\le 50$ ， $M\le 2500$ 。

对于 $70\%$ 的数据， $N\le 500$ ， $M\le 10^4$ 。

对于 $100\%$ 的数据： $1\le N\le 5000$ ， $1\le M\le 2\times 10^5$ ， $1\le Z_i \le 10^4$ ， $1\le X_i,Y_i\le N$ 。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$ 。

题解

1 篇题解

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

YuyiLv.6👑 站长管理员

P3366 【模板】最小生成树题解 Author: Yuyi 题意分析给定一个 $N$ 个节点、$M$ 条边的无向图，要求找到连通所有节点的最小生成树（MST），即选出 $N 1$ 条边使得图连通且边权之和最小。如果图本身就不连通，则输出 orz 。正解推导过程最小生成树最经典的算法是 Kruskal 算法，它本质上是贪心与并查集的完美结合。 1.…

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

2026年8月9日 22:35

P3366 【模板】最小生成树题解

Author: Yuyi

题意分析

给定一个 $N$ 个节点、 $M$ 条边的无向图，要求找到连通所有节点的最小生成树（MST），即选出 $N-1$ 条边使得图连通且边权之和最小。如果图本身就不连通，则输出 orz。

正解推导过程

最小生成树最经典的算法是 Kruskal 算法，它本质上是贪心与并查集的完美结合。

贪心：既然要总边权最小，我们就应该优先选择权值最小的边。因此，首先将所有的边按权值从小到大排序。
并查集维护连通性：按排序后的顺序依次遍历每条边。如果这条边连接的两个节点属于不同的集合（通过并查集 find 查询），说明它们尚未连通且加入该边不会产生环，我们就将这条边加入生成树中，并把这两个节点合并到一个集合。
结束条件：如果我们成功加入了 $N-1$ 条边，说明 $N$ 个节点已经全部连通，此时的权值和就是最小生成树的总权值。如果遍历完所有的边后，加入的边数仍然不到 $N-1$ 条，说明图不连通，输出 orz。

正解代码及分析

#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 = 200005; //根据最大边数2*10^5调整
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;
struct Edge
{
    int u,v;
    ll w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void solve()
{
    read(n),read(m);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    rep(i,1,n) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    ll ans = 0;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
        if(cnt == n-1) break;
    }
    if(cnt == n-1) cout << ans << endl;
    else cout << "orz" << 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 \log M)$ 。并查集的查询和合并配合路径压缩，单次操作接近 $O(1)$ ，处理所有的边耗时 $O(M)$ 。因此总体时间复杂度为 $O(M \log M)$ ，对于 $2 \times 10^5$ 的数据规模非常轻松。
空间复杂度：需要存储 $M$ 条边以及大小为 $N$ 的并查集父节点数组。根据咱们的开辟规范，直接采用了统一的 maxn 大小定义数组，因此总体空间复杂度为 $O(M)$ ，远低于题目的内存限制。

另一种解法：Prim 算法（堆优化）

除了 Kruskal 外，Prim 算法 也是求最小生成树的绝对主力，非常适合在点数不多、边数极大的稠密图下使用。

核心思想：从任意一个节点（通常选节点 1）开始，不断寻找与当前连通块相连的、边权最小的那条边，将新节点拉入连通块，直到 $N$ 个节点全部加入。
堆优化：为了快速找到边权最小的边，我们把与连通块相连的所有边扔进 priority_queue（小根堆）。每次取出堆顶元素，如果它指向的节点还没有被访问过，就标记为已访问，累加权值，并把该节点连出的所有新边也扔进堆里。
结束条件：当堆空时，如果选出的节点个数恰好等于 $N$ ，则连通；否则输出 orz。

Prim 算法代码及分析

#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 = 200005; //统一大小
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;
struct Node
{
    int v;
    ll w;
    bool operator<(Node A) const
    {
        return w > A.w; //小根堆
    }
};
vector<Node> e[maxn];
bool vis[maxn];
void solve()
{
    read(n),read(m);
    rep(i,1,m)
    {
        int u,v;
        ll w;
        read(u),read(v),read(w);
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    priority_queue<Node> q;
    q.push({1,0});
    int cnt = 0;
    ll ans = 0;
    while(!q.empty())
    {
        Node cur = q.top();
        q.pop();
        if(vis[cur.v]) continue;
        vis[cur.v] = true;
        ans += cur.w;
        cnt++;
        for(auto nxt : e[cur.v])
        {
            if(!vis[nxt.v]) q.push(nxt);
        }
    }
    if(cnt == n) cout << ans << endl;
    else cout << "orz" << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

Prim 复杂度分析：堆优化的 Prim 中，每个节点入堆出堆最多 $O(M)$ 次，优先队列（堆）的单次操作为 $O(\log M)$ ，因此总体时间复杂度同样是 $O(M \log M)$ ，与 Kruskal 平分秋色，均可畅快 AC。空间上使用了 vector 存储所有边，依然是 $O(M)$ 级别。

讨论

0 条讨论

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

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