P3366 【模板】最小生成树

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

时空限制：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

模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 struct edge{
 8     int a,b,c;
 9 }e[200100];
10 int n,m;
11 int far[5100];
12 int ans,cnt;
13 
14 int find(int a)
15 {
16     return far[a]==a?a:far[a]=find(far[a]);
17 }
18 bool cmp(edge a,edge b)
19 {
20     return a.c<b.c;
21 }
22 
23 int main()
24 {
25     scanf("%d%d",&n,&m);
26     for(int i=1;i<=n;++i) far[i] = i;
27     for(int i=1;i<=m;++i)
28     {
29         int a,b,c;
30         scanf("%d%d%d",&a,&b,&c);
31         e[i].a=a;
32         e[i].b=b;
33         e[i].c=c;
34     }
35     sort(e+1,e+m+1,cmp);
36     for(int i=1;i<=m;++i)
37     {
38         int aa = find(e[i].a);
39         int bb = find(e[i].b);
40         if(aa!=bb)
41         {
42             cnt++;
43             far[aa] = far[bb];
44             ans += e[i].c;
45             if(cnt==(n-1))break;
46         }
47     }
48     if(cnt==(n-1)) cout<<ans;
49     else cout<<"orz";
50     return 0;
51 }