当前位置：首页 > news >正文

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

news 2026/6/3 22:53:10

1.原题和原题链接

原题链接

P3366 【模板】最小生成树

题目描述

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

输入格式

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

接下来M MM行每行包含三个整数X i , Y i , Z i X_i,Y_i,Z_iXi,Yi,Zi，表示有一条长度为Z i Z_iZi的无向边连接结点X i , Y i X_i,Y_iXi,Yi。

输出格式

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

输入输出样例 #1

输入 #1

4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3

输出 #1

说明/提示

数据规模：

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

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

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

对于100 % 100\%100%的数据：1 ≤ N ≤ 5000 1\le N\le 50001≤N≤5000，1 ≤ M ≤ 2 × 10 5 1\le M\le 2\times 10^51≤M≤2×105，1 ≤ Z i ≤ 10 4 1\le Z_i \le 10^41≤Zi≤104，1 ≤ X i , Y i ≤ N 1\le X_i,Y_i\le N1≤Xi,Yi≤N。

样例解释：

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

2.主要思路

这道题是最小生成树的模板题，所以我们可以用Kruskal 算法+并查集解决。
首先我们需要明确题目的要求：找无向图中连接所有节点、总权值最小的边集，不连通就输出orz。Kruskal 算法的核心就是贪心：先把所有边按权值从小到大排序，再依次选则边，用并查集判断两点是否连通，不连通就选这条边，合并集合。
我的代码实现主要分为三步：一是初始化并查集，每个节点自己是父节点；二是排序所有边，保证从短边开始选；三是遍历边，用find找根节点，不同根就合并，累加权值，统计选边数。
最后判断：选够n-1条边就是连通的，那么就输出总权值；否则输出orz。

3.AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,fa[200005],s=0,sum=0;structshu{intx,y,z;}a[200005];boolcmp(shu c,shu v){returnc.z<v.z;}intfind(intx){if(fa[x]==x)returnx;elsereturnfa[x]=find(fa[x]);}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)fa[i]=i;for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].z;}sort(a+1,a+m+1,cmp);for(inti=1;i<=m;i++){intx1=find(a[i].x);inty1=find(a[i].y);if(x1!=y1){fa[x1]=y1;s+=1;sum+=a[i].z;}if(s==n-1)break;}if(s<n-1)cout<<"orz";elsecout<<sum;return0;}