CCF 201703-4 地铁修建(最小生成树)

题意：A市有n个交通枢纽，其中1号和n号非常重要，为了加强运输能力，A市决定在1号到n号枢纽间修建一条地铁。地铁由很多段隧道组成，每段隧道连接两个交通枢纽。经过勘探，有m段隧道作为候选，两个交通枢纽之间最多只有一条候选的隧道，没有隧道两端连接着同一个交通枢纽。现在有n家隧道施工的公司，每段候选的隧道只能由一个公司施工，每家公司施工需要的天数一致。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。作为项目负责人，你获得了候选隧道的信息，现在你可以按自己的想法选择一部分隧道进行施工，请问修建整条地铁最少需要多少天。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100000 + 10;

const int MAXT = 200000 + 10;

int fa[MAXN];

int Find(int x){

    return fa[x] = (fa[x] == x) ? x : Find(fa[x]);

}

struct Edge{

    int a, b, c;

    void read(){

        scanf("%d%d%d", &a, &b, &c);

    }

    bool operator < (const Edge&rhs)const{

        return c < rhs.c;

    }

}num[MAXT];

int main(){

    int n, m;

    scanf("%d%d", &n, &m);

    int a, b, c;

    for(int i = 0; i < m; ++i){

        num[i].read();

    }

    sort(num, num + m);

    for(int i = 1; i <= n; ++i) fa[i] = i;

    int ans;

    for(int i = 0; i < m; ++i){

        int x = Find(num[i].a);

        int y = Find(num[i].b);

        if(x == y) continue;

        if(x < y) fa[y] = x;

        else fa[x] = y;

        if(Find(n) == 1){

            ans = num[i].c;

            break;

        }

    }

    printf("%d\n", ans);

    return 0;

}