首页 > 代码库 > 洛谷 P1547 Out of Hay 题解
洛谷 P1547 Out of Hay 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=1547
题目背景
奶牛爱干草
题目描述
Bessie 计划调查N (2 <= N <= 2,000)个农场的干草情况，它从1号农场出发。农场之间总共有M (1 <= M <= 10,000)条双向道路，所有道路的总长度不超过1,000,000,000。有些农场之间存在着多条道路，所有的农场之间都是连通的。
Bessie希望计算出该图中最小生成树中的最长边的长度。
输入输出格式
输入格式：两个整数N和M。
接下来M行，每行三个用空格隔开的整数A_i， B_i和L_i，表示A_i和 B_i之间有一条道路长度为L_i。
输出格式：一个整数，表示最小生成树中的最长边的长度。
输入输出样例
输入样例#1：
3 31 2 232 3 10001 3 43
输出样例#1：
43
分析：
前面的东西还是套最小生成树的模板。在生成树的循环中，将ans改为记录当前的最长边。
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 6 using namespace std; 7 const int MAXN = 2010; 8 const int MAXM = 20010; 9 int fa[MAXN];10 11 struct edge12 {13 int f,t,v;14 }e[MAXM];15 16 struct edge tmp1,tmp2;17 int cmp(edge tmp1,edge tmp2)18 {19 return tmp1.v < tmp2.v;20 }21 22 int find(int x)23 {24 if(x == fa[x])25 return x;26 return fa[x] = find(fa[x]);27 }28 29 bool Union(int x,int y)30 {31 x = find(x),y = find(y);32 if(x != y)33 {34 fa[x] = y;35 return 1;36 }37 return 0;38 }39 40 inline void read(int &x)41 {42 char ch = getchar();char c;x = 0;43 while(ch > ‘9‘ || ch < ‘0‘) c = ch,ch = getchar();44 while(ch <= ‘9‘ && ch >= ‘0‘) x = x*10+ch-‘0‘,ch = getchar();45 }46 47 int main()48 {49 int m,n;50 read(n),read(m);51 for(int i = 1;i <= m;i ++)52 read(e[i].f),read(e[i].t),read(e[i].v);53 for(int i = 1;i <= n;i ++)54 fa[i] = i;55 sort(e+1,e+1+m,cmp);56 int cnt = n,ans = 0;57 for(int i = 1;i <= m &&cnt > 1;i ++)58 {59 if(Union(e[i].f,e[i].t))60 ans = max(ans,e[i].v),cnt --;61 //ans记录生成树中的最长边。这里一定要注意cnt，最小生成树一旦形成立刻退出62 }63 printf("%d\n",ans);64 return 0;65 }
洛谷 P1547 Out of Hay 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。