题目描述

A 市有 n 个交通枢纽，其中 1 号和 n 号非常重要，为了加强运输能力，A 市决定在 1 号到 n 号枢纽间修建一条地铁。
地铁由很多段隧道组成，每段隧道连接两个交通枢纽。

经过勘探，有 m 段隧道作为候选，两个交通枢纽之间最多只有一条候选的隧道，没有隧道两端连接着同一个交通枢纽。
现在有 n 家隧道施工的公司，每段候选的隧道只能由一个公司施工，每家公司施工需要的天数一致。
而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。
作为项目负责人，你获得了候选隧道的信息，现在你可以按自己的想法选择一部分隧道进行施工，请问修建整条地铁最少需要多少天。

输入格式
输入的第一行包含两个整数 n,m，用一个空格分隔，分别表示交通枢纽的数量和候选隧道的数量。

第 2 行到第 m+1 行，每行包含三个整数 a,b,c，表示枢纽 a 和枢纽 b 之间可以修建一条隧道，需要的时间为 c 天。

输出格式
输出一个整数，修建整条地铁线路最少需要的天数。

数据范围
对于 20% 的评测用例，1≤n≤10，1≤m≤20；
对于 40% 的评测用例，1≤n≤100，1≤m≤1000；
对于 60% 的评测用例，1≤n≤1000，1≤m≤10000，1≤c≤1000；
对于 80% 的评测用例，1≤n≤10000，1≤m≤100000；
对于 100% 的评测用例，1≤n≤100000，1≤m≤200000，1≤a,b≤n，1≤c≤1000000。
所有评测用例保证在所有候选隧道都修通时1号枢纽可以通过隧道到达其他所有枢纽。

样例

输入样例：

6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6

输出样例：

6

算法1

Kruskal

因为只需要1-n所需要的天数,所以当1-n是连通的时候直接输出当前的 res 就行，res取沿途天数的最大值

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
int n,m;
int p[N];
struct Edge
{
    int a,b,w;
    bool operator<(const Edge &W)const
    {
        return w < W.w;
    }
}edge[N*2];
void init()
{
    for(int i=1;i<=n;++i) p[i] = i;
}
int find(int x)
{
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int main()
{
    cin>>n>>m;
    init();
    for(int i=0;i<m;++i)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edge[i] = {a,b,w};
    }
    sort(edge,edge+m);
    int res =0;
    for(int i=0;i<m;++i)
    {
        auto e = edge[i];
        int a = e.a;a = find(a);
        int b = e.b;b = find(b);
        int w = e.w;
        if(a != b)
        {
            p[a] = b;
            res = max(res,w);
            if(find(1) == find(n))
            {
                cout<<res;
                return 0;
            }
        }
    }
    return 0;
}