洛谷P1111-修复公路-题解

修复公路

题目背景

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出 A 地区的村庄数 $N$，和公路数 $M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 $1$ 行两个正整数 $N,M$。

下面 $M$ 行，每行 $3$ 个正整数 $x,y,t$，告诉你这条公路连着 $x,y$ 两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 $-1$，否则输出最早什么时候任意两个村庄能够通车。

样例 #1

样例输入 #1

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

样例输出 #1

5

提示

$1\leq x, y\leq N \le 10 ^ 3$，$1\leq M, t \le 10 ^ 5$。

P1111 修复公路 - 洛谷

思路

先将修路的时间进行排序，每过一天合并两个村庄，当所有的村庄都被合并到并查集中了，说明村庄之间至少有一条修复完成的道路了。

C++ 代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

class UnionFindSet {
public:
    vector<int> trees, size;

    explicit UnionFindSet(int len) : trees(len), size(len, 1) {
        iota(trees.begin(), trees.end(), 0);
    }

    int find(const int &x) {
        int tmp;
        for (tmp = x; trees[tmp] != tmp; tmp = trees[tmp]);
        return tmp;
    }

    void unite(const int &x, const int &y) {
        int &&fx = find(x), &&fy = find(y);
        size[fx] <= size[fy] ? trees[fx] = fy : trees[fy] = fx;
        if (size[fx] == size[fy] and fx != fy)
            size[fy]++;
    }

    bool isOneSet() {
        for (int res = 0, i = trees.size() - 1; i >= 1; --i) {
            if (trees[i] == i)
                ++res;
            if (res == 2)
                return false;
        }
        return true;
    }
};

bool cmp(const pair<pair<int, int>, int> &a,
         const pair<pair<int, int>, int> &b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<pair<int, int>, int> > mat(m);
    vector<int> time(m);
    UnionFindSet ufs(n + 1);
    for (int i = 0; i < m; ++i)
        cin >> mat[i].first.first >> mat[i].first.second >> mat[i].second;
    sort(mat.begin(), mat.end(), cmp);
    for (int i = 0; i < m; ++i) {
        ufs.unite(mat[i].first.first, mat[i].first.second);
        if(ufs.isOneSet()) {
            cout << mat[i].second;
            return 0;
        }
    }
    cout << -1;
    return 0;
}