最小生成树
题目链接:
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出orz
输入格式
第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)
接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi
输出格式
输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz
输入输出样例
输入 #1
4 51 2 21 3 21 4 32 3 43 4 3
输出 #1
7
说明/提示
时空限制:1000ms,128M
数据规模:
对于20%的数据:N<=5,M<=20
对于40%的数据:N<=50,M<=2500
对于70%的数据:N<=500,M<=10000
对于100%的数据:N<=5000,M<=200000
样例解释:
所以最小生成树的总边权为2+2+3=7。
思路:最小生成树的简单模板题
//// Created by hy on 2019/7/28.//#include#include #include #include #include #include using namespace std;typedef long long ll;const int maxn=2e5+10;ll father[maxn];ll n,ans,point,m;struct Node{ int u,v,w; bool operator<(const Node other)const{ return this->w