# P3366 【模板】最小生成树 https://www.luogu.com.cn/problem/P3366## 题目描述如题给出一个无向图求出最小生成树如果该图不连通则输出 orz。## 输入格式第一行包含两个整数 $N,M$表示该图共有 $N$ 个结点和 $M$ 条无向边。接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。## 输出格式如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。## 输入输出样例 #1### 输入 #14 51 2 21 3 21 4 32 3 43 4 3### 输出 #17## 说明/提示数据规模对于 $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$。样例解释所以最小生成树的总边权为 $2237$。#include iostream #include algorithm using namespace std; int n,m,f[5010]; int sum; struct node{ int x,y,l; }a[200001]; int dev(int x){ if(xf[x]){ return x; } return dev(f[x]); } void op(int x,int y,int o){ int nxdev(x),ny dev(y); if(nx ! ny){ f[nx]ny; sumo; n--; } } bool cmp(node i,node j) { return i.lj.l; } int main() { cinnm; for (int i1;in;i) { f[i]i; } for (int i1;im;i) { cina[i].xa[i].ya[i].l; } sort(a1,am1,cmp); for(int i1;im;i) { op(a[i].x,a[i].y,a[i].l); if(n1){ coutsum\n; return 0; } } coutorz; }