题目描述
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.
输出格式
一个整数, 表示最小生成树中的最长边的长度.
要把所有点连通, 不难想到我们需要构建一棵生成树.
题目要求最长边最短, 我们根据 Kruskal 的贪心思想, 可以对边排序之后优先加小的边, 用并查集维护生成树, 最后加入的边就是答案.
时间复杂度为 O(MlogM)
- #include<algorithm>
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #define maxn 2001
- #define maxm 10001
- using namespace std;
- int n,m;
- inline int read(){
- register int x(0),f(1); register char c(getchar());
- while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
- while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- struct edge{
- int u,v,w;
- bool operator<(const edge &e)const{ return w<e.w; }
- }e[maxm];
- int fa[maxn],ans;
- int get(int x){ return fa[x]==x?x:fa[x]=get(fa[x]); }
- inline void kruskal(){
- sort(e+1,e+1+m);
- for(register int i=1;i<=n;i++) fa[i]=i;
- for(register int i=1;i<=m;i++){
- int u=e[i].u,v=e[i].v,w=e[i].w;
- if(get(u)==get(v)) continue;
- fa[get(u)]=get(v),ans=w;
- }
- }
- int main(){
- n=read(),m=read();
- for(register int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();
- kruskal();
- printf("%d\n",ans);
- return 0;
- }
[Usaco2005 Mar]Out of Hay 干草危机
来源: http://www.bubuko.com/infodetail-3099717.html