洛谷P1547 Out of Hay 最小生成树

题目背景

奶牛爱干草

题目描述

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。

输出格式

一个整数，表示最小生成树中的最长边的长度。

//两个整数N和M。
//接下来M行，每行三个用空格隔开的整数A_i， B_i和L_i，表示A_i和 B_i之间有一条道路长度为L_i。
#include<iostream>
#include<algorithm>
using namespace std;

const int maxv = 2e3+5;
const int maxe = 1e4+5;

struct Eage{
    int from;
    int to;
    int len;
}arr[maxe];
int father[maxv];

bool cmp(Eage a,Eage b)
{
    return a.len<b.len;
}

void init()
{
    for(int i=1;i<maxv;++i)
    {
        father[i]=i;
    }
}

int find(int x)
{
    if(x==father[x])
    {
        return x;    
    }
    return father[x]=find(father[x]);
}

void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        father[p]=q;
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        return true;
    }else 
    {
        return false;
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        init();
        for(int i=1;i<=m;++i)
        {
            cin>>arr[i].from>>arr[i].to>>arr[i].len;
        }    
        sort(arr+1,arr+m+1,cmp);
        
        int ans=-1<<30;
        int cnt=0;
        for(int i=1;i<=m;++i)
        {
            if(judge(arr[i].from,arr[i].to))
            {
                merge(arr[i].from,arr[i].to);
                cnt++;
                if(arr[i].len>ans)
                {
                    ans=arr[i].len;
                }
            }
            if(cnt==n-1)
            {
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}