题目链接

https://www.luogu.org/problemnew/show/P3366

题目描述

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

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

思路

这是一道模板题！！！

我做了半个小时！！

就是因为忘记初始化！！！

在这里提醒自己......

这道题有两个做法，我用的是Kruskal算法

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>
using namespace std; int n,m,k; int ans=0; int pre[5050]; struct point { int x,y,w; } a[200010]; int find(int x) { if(pre[x]==x)return x; else { pre[x]=find(pre[x]); return pre[x]; } } bool cmp(point a,point b) { return a.w<b.w; } void init(){ for(int i=1;i<=n;i++) pre[i]=i; } int main() { scanf("%d%d",&n,&m); init(); for(int i=1; i<=m; i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); } sort(a+1,a+1+m,cmp); for(int i=1; i<=m; i++) { if(find(a[i].x)!=find(a[i].y)) { pre[find(a[i].x)]=find(a[i].y); ans+=a[i].w; k++; } if(k==n-1)break; } cout<<ans<<'\n'; return 0; }