题目链接：
https://vjudge.net/problem/POJ-1861
题目大意：
有一些公司，公司之间需要连接起来。给出了哪些公司可以连接以及连接边的长度。求最小生成树中最大的边，以及最小生成树的边数，以及输出一颗可行的最小生成树。
思路：
裸的kruskal
这里要求输出的是最大边和边数，不是权值，而且样例是错误的
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<sstream>10 using namespace std;11 typedef long long ll;12 const int maxn = 1e5 + 10;13 const int INF = 1 << 30;14 int dir[4][2] = {1,0,0,1,-1,0,0,-1};15 int T, n, m;16 struct edge17 {18 ????int u, v, w;19 ????bool operator <(const edge& a)const20 ????{21 ????????return w < a.w;22 ????}23 };24 edge a[maxn], ans[1010];25 int tot, maxx;26 int par[1010], high[1010];27 //初始化n个元素28 void init(int n)29 {30 ????for(int i = 0; i < n; i++)31 ????{32 ????????par[i] = i;33 ????????high[i] = 0;34 ????}35 }36 //查询树的根37 int Find(int x)38 {39 ????return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩40 }41 void unite(int x, int y)42 {43 ????x = Find(x);44 ????y = Find(y);45 ????if(x == y)return;46 ????if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y47 ????else48 ????{49 ????????par[y] = x;50 ????????if(high[x] == high[y])high[x]++;51 ????}52 }53 bool same(int x, int y)54 {55 ????return Find(x) == Find(y);56 }57 int kruskal(int n, int m)//点数n，边数m58 {59 ????int sum_mst = 0;//mst权值60 ????int num= 0;//已经选择的边的边数61 ????sort(a, a + m);//边进行排序62 ????init(n);//初始化并查集63 ????for(int i = 0; i < m; i++)64 ????{65 ????????int u = a[i].u;66 ????????int v = a[i].v;67 ????????if(Find(u - 1) != Find(v - 1))//图最开始的下标是1，并查集是068 ????????{69 ????????????//printf("%d %d %d\n", u, v, a[i].w);70 ????????????ans[tot++] = a[i];71 ????????????maxx = max(maxx, a[i].w);72 ????????????sum_mst++;73 ????????????num++;74 ????????????unite(u - 1, v - 1);75 ????????}76 ????????if(num >= n - 1)break;77 ????}78 ????return sum_mst;79 ????//printf("weight of mst is %d\n", sum_mst);80 }81 int main()82 {83 ????while(cin >> n >> m)84 ????{85 ????????tot = maxx = 0;86 ????????for(int i = 0; i < m; i++)87 ????????{88 ????????????scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);89 ????????}90 ????????int sum = kruskal(n, m);91 ????????cout<<maxx<<endl;92 ????????cout<<sum<<endl;93 ????????for(int i = 0; i < tot; i++)94 ????????????cout<<ans[i].u<<" "<<ans[i].v<<endl;95 ????}96 ????return 0;97 }POJ-1861 Network---最小生成树
原文地址：https://www.cnblogs.com/fzl194/p/8724555.html