题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define max 200005 typedef struct graph { int edga_first,edga_second; int e; } Node; int arr[max],rank[max]; Node a[max]; int cmp(const void*a, const void *b) { return ((Node*)a)->e - ((Node*)b)->e; } void Init(int n) { for(int i=1; i<=n; i ) { arr[i]=i; rank[i]=1; } } int find(int x) { if(x==arr[x]) { return x; } else { return arr[x]=find(arr[x]); } } void unite(int x,int y) { x=find(x); y=find(y); if(x==y) { return; } if(rank[x]<rank[y]) { arr[x]=y; } else { arr[y]=x; if(rank[x]==rank[y]) { rank[y] ; } } } int kruskal(int n,int m) { int result=0,n_edge=0,f1,f2,j=1; for(int i=1; i<=m; i ) { f1=find(arr[a[i].edga_first]); f2=find(arr[a[i].edga_second]); if(f1!=f2) { unite(f1,f2); result =a[i].e; n_edge ; } if(n_edge==n-1) { return result; } } return -1; } int main() { int n,m,p,q,ans; scanf("%d%d",&n,&m); Init(n); for(int i=1; i<=m; i ) { scanf("%d%d%d",&a[i].edga_first,&a[i].edga_second,&a[i].e); } qsort(a,m,sizeof(a[0]),cmp); p=kruskal(n,m); if(p==-1) { printf("orz"); }else{ printf("%d",p); } return 0; }