题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1复制
1. 4 5 2. 1 2 2 3. 1 3 2 4. 1 4 3 5. 2 3 4 6. 3 4 3
输出 #1复制
7
说明/提示
数据规模：
对于 20% 的数据， N≤5， M≤20。
对于 40% 的数据，N\le 50N≤50，M\le 2500M≤2500。
对于 70% 的数据，N\le 500N≤500，M\le 10^4M≤104。
对于 100% 的数据： 1≤N≤5000， 1≤M≤2×10^5 1≤Zi≤10^4 。
样例解释：
所以最小生成树的总边权为 2+2+3=72+2+3=7。
#include<bits/stdc++.h> using namespace std; int p[310]; struct edge{ int a,b,w; bool operator<(const edge&a)const{ return w<a.w;//小到大 } }s[10010]; int find(int x){//根节点 if (x!=p[x]) return find(p[x]); return p[x]; } int main(){ int n,m,k; cin>>m>>n; if(n==0) return 0; for(int i=0;i<n;i++){//几条路 int a,b,c; scanf("%d%d%d",&a,&b,&c);//c代表权值 s[i]={a,b,c};//结构体写法 } sort(s,s+n,cmp);//排列方式按照结构体里面的排列来 就是小到大 for(int i=1;i<310;i++){ p[i]=i;//自己是自己的根节点 } int num=0,maxn=0; for(int i=0;i<n;i++){ int a1=find(s[i].a); int b1=find(s[i].b); if(a1!=b1){ p[a1]=b1; maxn=maxn+s[i].w; } } cout<<maxn<<endl;//几条路和最大值 return 0;//听懂掌声 }
